백준 1253 좋다

문제

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

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

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

---

코드

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

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));

        //n과 배열 입력 받고 오름차순 정렬
        int n = Integer.parseInt(br.readLine());
        int[] array=new int[n];
        StringTokenizer st = new StringTokenizer(br.readLine());
        for (int i = 0; i < n; i++)
            array[i] = Integer.parseInt(st.nextToken());

        Arrays.sort(array);

        int count=0;
        //i는 만들고 싶은 수의 인덱스
        for(int i=0; i<n; i++){
            //j는 더하는 두 수 중 하나
            for(int j=0; j<n; j++){
                //i와 j가 같으면 패스
                if(i==j)
                    continue;

                //만들어진다면 카운트하고 다음 만들 수 탐색
                if(binarySearch(array, j, i)){
                    count++;
                    break;
                }
            }
        }

        System.out.println(count);
    }

    //만들어지는 지 이진 탐색으로 찾고 만들어진다면 true 리턴
    public static boolean binarySearch(int[] array, int index, int x){
        int start=0;
        int end=array.length;

        while(start<end){
            int mid=(start+end)/2;

            if(array[x]>array[index]+array[mid])
                start=mid+1;
            if(array[x]<array[index]+array[mid])
                end=mid;
            //두 수를 더한 값이 같다면
            if(array[x]==array[index]+array[mid]){
                //mid 값이 만들 수와 다른 한 숫자와 다른 숫자라면 true 리턴
                if(x!=mid && index!=mid)
                    return true;

                //값이 같고 인덱스가 다른 수가 있는 지 선형 탐색
                int target=array[mid];

                //mid를 1씩 증가시키다가 값은 같고 다른 두 수와 인덱스가 다르다면 true
                int temp=mid;
                while(temp<array.length-1){
                    if(array[++temp]==target){
                        if(temp!=index && temp!=x)
                            return true;
                    }
                    else
                        break;
                }

                //mid를 1씩 감소시키다가 값은 같고 다른 두 수와 인덱스가 다르다면 true
                temp=mid;
                while(temp>0){
                    if(array[--temp]==target){
                        if(temp!=index && temp!=x)
                            return true;
                    }
                    else
                        break;
                }

                //충족되는 수가 없으면 해당 수는 두 수의 합이 될 수 없다.
                return false;
            }
        }

        return false;
    }
}

---

해결 과정

1. O(N^2 * log N)으로 가능하다. 0번부터 N-1번까지 모든 수에 대해서 탐색한다. 해당 수를 만들기 위해서 0번부터 N-1번까지의 수를 각각 기준으로 잡고 이진탐색으로 다른 수가 존재하는 지 검사한다.

2. 😁