[BOJ3273] 수 정렬하기

배열의 활용에 대해 좀 더 고민해 볼 수 있는 문제.

 

 

 

1. 처음에는 모든 경우를 다 돌도록 이중 for문을 사용했으나 바로 시간 초과가 났다.

import java.io.*;
import java.nio.Buffer;

//https://www.acmicpc.net/problem/3273
public class Main {

    public static void main(String[] args) throws IOException {

        //단순한 방법 --> 시간초과 남
        //모든 수를 더해본다
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

        int N = Integer.parseInt(br.readLine());
        String[] num = br.readLine().split(" ");
        int result = Integer.parseInt(br.readLine());
        int cnt = 0;
        for(int i=0;i<N;i++) {
            for (int j = i + 1; j < N; j++) {
                int sum = Integer.parseInt(num[i]) + Integer.parseInt(num[j]);
                if(sum == result) cnt++;
            }
        }
        bw.write(cnt + "");
        bw.flush();
    }

}

시간 초과가 남.

 

 

2. 강의를 들으며 배열을 다른 방식으로 사용해 보기로 했다.

 

1) 숫자 기록 배열 만들기

해당 수가 있는지 확인하는 불린타입 배열을 만든다. (중복이 없다고 했으므로 카운트가 아닌 불린으로 만든다.)

boolean[] exist = new boolean[1000001]; // 문제에서 수의 범위가 백만이라고 했기 때문에 

단, 수를 1부터 카운트 할 것이기 때문에 인덱스를 1부터 사용할 것이므로 1000001 크기의 배열을 만든다.

그 후, exist 배열에 입력받은 수를 인덱스로 넣어준다.

  for(int i=0; i<N; i++)
            exist[a[i]] = true;

 

2) (X-1)/2 (X는 결과값) 만큼 for문을 돈다.

예를 들어,

* input : 1 2 3 4 5 6 7 8 * 합산값 : 9

---> 나올 수 있는 쌍: (1,8) / (2,7) / (3,6) / (4,5) / (5,4) / (6,3) / (7,2) / (8,1)  ---> 총 8개 ---> 답은 4개

이 경우 중복되는 쌍들은 카운트할 필요가 없다.

따라서 합산값에 2를 나눈 몫만큼만 for문을 돈다. (X/2)

 

단, 합산값이 짝수일 경우 

* input : 1 2 3 4 5 6 7 8 * 합산값 : 8

---> 나올 수 있는 쌍: (1,7) / (2,6) / (3,5) / (4,4) / (5,3) / (6,2) / (7,1)  ---> 총 7개 ---> 답은 3개

합산값이 짝수일 경우 (4,4)라는 동일 값이 순서쌍으로 생겨날 수 있으므로 1을 빼서 (어차피 동일한 숫자는 하나밖에 없으므로)

(X-1)/2 만큼을 반복문을 돌린다.

 

최종으로 작성한 코드는 아래와 같다.

import java.util.Scanner;

//https://www.acmicpc.net/problem/3273
public class BOJ3273Re {

    public static void main(String[] args){

        Scanner sc = new Scanner(System.in);
        int N = sc.nextInt();
        int[] a = new int[N];
        for (int i=0; i< N; i++)
            a[i] = sc.nextInt();
        int X = sc.nextInt();

        boolean[] exist = new boolean[1000001]; //숫자 기록배열
        for(int i=0; i<N; i++)
            exist[a[i]] = true;

        int ans = 0;
        for(int i=1; i<=(X-1)/2;i++)
            if(i<=1000000 && X-i <= 1000000) //범위 체크 필수
                ans += (exist[i] && exist[X-i]) ? 1 : 0; //동일 쌍이 있으면 카운트를 해준다.
        System.out.println(ans);
    }

}

 

 

https://www.acmicpc.net/problem/3273

3273번: 두 수의 합