Java - [BOJ]1253 - 좋다

출처

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

 

문제

 

N개의 수가 주어질 때, 어떤 수가 다른 두 수의 합으로 나타낼 수 있다면 그것을 좋은수라고 하는데, 그 갯수를 구하는 문제이다.

 

풀이

먼저, 당연한 말이지만 주어진 N개의 수가 3개 미만이라면, 다른 두 수가 없기때문에 좋은수가 될 수 없다.

 

다른 두 수를 이용해 합으로 나타낼 수 있는지 알아보려면, 투 포인터 개념을 활용하여 직접 비교해보는 방법 밖에 없다.

 

하지만 모든 경우를 다 무작정 비교하게 되면, 기준이 되는 원소를 고르는 for문 하나, i j 인덱스를 통해 합이 성립하는지 확인하기 위한 for문이 2개, 총 3개의 반복문을 가진다. N^3 복잡도를 가진 코드는 매우 비효율적인 알고리즘이며 사용하지 않아야 한다.

 

그렇기 때문에 우리는 이것을 단순 무식하게 모두 돌지 않고 중간에 조건을 추가해주어 효율적으로 비교할 수 있도록 해야한다.

 

투 포인터를 활용하기 위해서는 먼저, 정렬이 선행되어야 한다. 그래야 효율적으로 투 포인터 활용 로직을 구성할 수 있기 때문이다.

 

정렬이 되었다면 주어진 수 중 제일 작은 수를 i로, 제일 큰 수를 j로 두어 탐색을 시작한다. 왜 기준원소의 앞인 k-1을 j로 하지 않는가? 만약 기준원소 k가 7이고 j가 8이라면 더해서 작아질일이 없지 않은가? 라고 생각했다면 문제를 다시 한번 살펴야 한다. 위 질문에 대한 답은 바로 양수만 주어지는 것이 아닌, 음수 또한 주어지기 때문이다. k가 7이고 j가 8이라면, i가 -1인 경우에는 좋은수가 될 수 있다. 아래 예시를 생각해서 풀어보면 좋을 것이다.

 

8
-1 0 2 3 5 6 7 9

 

만약 i번째와 j번째 원소의 합이 기준원소인 K보다 크다면? K보다 오른쪽에 위치한(큰 쪽에 위치한) j를 줄여가며 탐색을 진행하고, 만약 반대로 K보다 작다면 i를 올려가며 탐색을 진행하면 K와 가까워질 수 있다.

 

이제 코드를 보며 이해하면 훨씬 쉬울 것이다.

 

코드

import java.io.*;
import java.util.*;

public class Main {
    static int N;
    static int[] arr;

    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

        StringTokenizer st = new StringTokenizer(br.readLine(), " ");
		N = Integer.parseInt(st.nextToken());

        arr = new int [N];

        int answer = 0;
        

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

        Arrays.sort(arr);

        for (int x = 0; x < N; x++) {
            int i = 0;
            int j = N-1;
            while (i < j) {
                if (arr[i] + arr[j] == arr[x]) {
                    if (i != x && j != x) {
                        answer++;
                        break;
                    } else if (i == x) {
                        i++;
                    } else {
                        j--;
                    }
                } else if (arr[i] + arr[j] > arr[x]) {
                    j--;
                } else {
                    i++;
                }
            }
        }

        bw.write(answer + "\n");

        br.close();
        bw.flush();
        bw.close();
    }

}