백준 1253 - 좋다

문제

시간제한 2초

N개의 수 중에서 어떤 수가 다른 수 두 개의 합으로 나타낼 수 있다면 그 수를 “좋다(GOOD)”고 한다.

N개의 수가 주어지면 그 중에서 좋은 수의 개수는 몇 개인지 출력하라.

수의 위치가 다르면 값이 같아도 다른 수이다.

입력

첫째 줄에는 수의 개수 N(1 ≤ N ≤ 2,000), 두 번째 줄에는 i번째 수를 나타내는 $A_i$가 N개 주어진다. (|$A_i$| ≤ 1,000,000,000, $A_i$는 정수)

출력

좋은 수의 개수를 첫 번째 줄에 출력한다.

문제 풀이

예제 입력1

10
1 2 3 4 5 6 7 8 9 10

문제를 먼저 이해해보자면 주어진 N개의 수들 중에서 다른 두 수의 합으로 표현되는 수가 있다면 그 수를 '좋은 수'라 칭하고 갯수를 출력하면 되는 문제이다.

위에 예시로 10을 표현할수 있는 두 개의 수는 (1, 9) ,(2, 8), (3, 7), (4, 6) 등이 있으니 10은 좋은 수가 맞다.

이런 식으로 한 개의 수를 계산하는데 걸리는 시간 복잡도가 $N^2$보다 작아야 한다. 따라서 최소 $O(nlogn)$ 의 시간 복잡도를 가져야 한다.

정렬과 투 포인터 알고리즘을 사용하면 가능하다.

위의 그림과 같이 찾으려는 값 find = 10이고

start_index = 0, end_index = 9 일때

배열 A안에 값들이 있다는 가정 하에 A[0] + A[9] = 11

찾으려는 값 find 보다 크기 때문에 end_index를 1씩 빼주면서 K와 같은 값이 될때까지 찾는 방식으로 진행하면 된다.

이 때 주의해야 할 점은 $A_i$가 정수이기 때문에 0도 포함될 수 있다는 사실이다.

만약 찾으려는 값이 8이면 0 + 8은 정답이 아니다.

찾으려는 값이 포함되어 있으면 서로 다른 두 수의 합에 맞지 않기 때문이다.

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.StringTokenizer;

class 좋다 {

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        int N = Integer.parseInt(br.readLine());
        int A[] = new int[N];

        StringTokenizer st = new StringTokenizer(br.readLine());
        for(int i = 0; i < N; i++){
            A[i] = Integer.parseInt(st.nextToken());
        }

        Arrays.sort(A);
        int count = 0;

        for(int i = 0; i < N; i++) {

            int find = A[i];
            int start_index = 0;
            int end_index = N - 1;

            while(start_index < end_index){
                if(A[start_index] + A[end_index] == find) {
                	// 주의!!
                    if(start_index != i && end_index != i){
                        count++;
                        break;
                    } else if(start_index == i) {
                        start_index++;
                    } else if(end_index == i){
                        end_index--;
                    }
                }else if(A[start_index] + A[end_index] > find) {
                    end_index--;
                }else {
                    start_index++;
                }
            }
        }
        System.out.println(count);
    }
}
    

회고

문제를 보고 정렬과 투 포인터 방식을 사용해야 한다는 생각이 정말 1도 들지 않았다. 그만큼 문제를 많이 풀어봐야 어느 정도 접근할 수 있다는 것을 깨달았다. Do it! 알고리즘 코딩 테스트를 참고해야 그나마 문제가 풀리니 스스로 풀어보는 방법도 터득해 나가야 겠다.