[백준]좋다 1253

문제

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

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

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

입력

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

출력

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

예제 입력 1 

10
1 2 3 4 5 6 7 8 9 10

예제 출력 1 

8

 

이 문제를 들어온 num의 갯수만큼 돌면서 하나하나 비교하다보면 O(n) * O(n) * O(n)의 시간 복잡도가 걸린다. 

총 2000개의 숫자가 나올 수 있으므로 2000^3은 8,000,000,000 즉 8초의 시간이 걸리게 된다.

이를 줄이기 위해 정렬시킨 후 binary Search를 사용하면 O(nlogn) + O(n) * O(n) * O(logn)이 나오게 되어 충분히 동작할 수 있다.

a + b = i를 다른 말로 하면 i - a = b 가 될 수 있다.

i에서 a를 뺀 후 b가 존재하는지 찾으면 a가 좋은 숫자인지 알 수 있다는 것이다.

b를 찾는것을 binary Search로 돌려보면 된다.

 

주의해야 할 점은 자기 자신인 i나 a를 두번 선택하는 것을 막기 위해 flag 배열을 만들어 사용하였다.

 

풀이 코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.PrintWriter;
import java.util.*;

public class 좋다_1253 {
    public static void main(String[] args) throws IOException {

        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        PrintWriter pw = new PrintWriter(System.out);

        int n = Integer.parseInt(br.readLine());
        int[] num = new int[n];
        StringTokenizer st = new StringTokenizer(br.readLine());

        for (int i = 0; i < n; i++) {
            num[i] = Integer.parseInt(st.nextToken());
        }

        Arrays.sort(num);

        int cnt = 0;

        boolean[] visit = new boolean[n];
        boolean[] flag = new boolean[n];
        boolean[] flagA = new boolean[n];

        for(int i = 0; i<num.length; i++){
            flag[i] = true;
            for(int a = 0; a<num.length; a++){

                if(flag[a]) {
                    continue;
                }
                flagA[a] = true;

                int b = num[i] - num[a];

                int left = 0;
                int right = num.length-1;
                int mid = 0;

                while(right >= left){

                    mid = (left + right)/2;

                    if(num[mid] > b) {
                        right = mid-1;
                    } else if(num[mid] < b) {
                        left = mid+1;
                    } else {
                        if(flagA[mid] || flag[mid]) {
                            int r = mid;
                            while((r>= 0 && r<=num.length-1)&& (num[mid] == num[r])) {

                                if((!flag[r] && !flagA[r])) {
                                    visit[i] = true;
                                    break;
                                }
                                r++;
                            }
                            break;

                        } else {
                            visit[i] = true;
                            break;
                        }
                    }
                }
                flagA[a] = false;
            }
            flag[i] = false;
        }

        for(int i = 0; i< visit.length; i++) {
            if(visit[i]) {
                cnt++;
            }
        }

        pw.println(cnt);

        br.close();
        pw.close();

    }
}