[JAVA] 백준 (실버4) 1920번 수 찾기

링크

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

---

문제 설명

정답률 30.130%
N개의 정수 A[1], A[2], …, A[N]이 주어져 있을 때, 이 안에 X라는 정수가 존재하는지 알아내는 프로그램을 작성하시오.

---

입력 예제

• 첫째 줄에 자연수 N(1 ≤ N ≤ 100,000)이 주어진다.
• 다음 줄에는 N개의 정수 A[1], A[2], …, A[N]이 주어진다.
• 다음 줄에는 M(1 ≤ M ≤ 100,000)이 주어진다.
• 다음 줄에는 M개의 수들이 주어지는데, 이 수들이 A안에 존재하는지 알아내면 된다.
• 모든 정수의 범위는 -231 보다 크거나 같고 231보다 작다.

5
4 1 5 2 3
5
1 3 7 9 5

---

출력 예제

• M개의 줄에 답을 출력한다. 존재하면 1을, 존재하지 않으면 0을 출력한다.

1
1
0
0
1

---

풀이

N과 M의 최대값이 $10^5$이므로 단순 반복문으로는 풀 수 없다. 이진 탐색은 $O(log(n))$의 시간복잡도를 갖는다. N의 대해서 이진 탐색을 진행한다고 하면 반틈씩 쪼개가면서 탐색을 하므로 다음과 같다.

• loop 1: $1/2*N$
• loop 2: $(1/2)^2*N$
  ...
• look K: $(1/2)^K*N$

최악의 경우 K번째에서 쪼개진 크기가 1이 되므로 $(1/2)^K*N=1$이 되고 이를 정리하면 $log_2(N) = K$가 나온다. 이 문제는 M개의 수에 대해 탐색을 하므로 $O(nlog(n))$ 시간 복잡도로 해결할 수 있다.

이진 탐색 자체는 간단하지만 탐색할 배열을 무조건 정렬을 한 뒤 인덱스를 잘 설정해야 한다.

start = 0;
end = N - 1;
mid = (start + end) / 2;

그리고 start와 end가 같아질 때까지 반복을 진행하는데 다음의 기준을 둔다.

• 중앙값의 왼쪽에 타겟: end = mid - 1
• 중앙값의 오른쪽에 타겟: start = mid + 1

타겟의 위치에 따라 중앙값을 갱신시켜 나가며 중앙값이 타겟과 일치되는 때를 찾는다.

while (start <= end) {
    mid = (start + end) / 2;
    if (arr[mid] > target) {
        end = mid - 1;
    } else if (arr[mid] < target) {
        start = mid + 1;
    } else {
        found = true;
        break;
    }
}

코드

//백준
public class Main {

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

        System.setIn(new FileInputStream("src/input.txt"));
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st;
        StringBuilder sb = new StringBuilder();

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

        int M = Integer.parseInt(br.readLine());  //10^5
        int[] arr2 = new int[M];
        st = new StringTokenizer(br.readLine());
        for (int i = 0; i < M; i++) {
            arr2[i] = Integer.parseInt(st.nextToken());
        }

        Arrays.sort(arr);

        for (int target : arr2) {
            boolean found = false;
            int start = 0;
            int end = N - 1;

            //start와 end가 같아질 때까지 반복
            while (start <= end) {
                int mid = (start + end) / 2;
                if (arr[mid] > target) {
                    end = mid - 1;
                } else if (arr[mid] < target) {
                    start = mid + 1;
                } else {
                    found = true;
                    break;
                }
            }
            if (found) {
                sb.append(1).append("\n");
            } else {
                sb.append(0).append("\n");
            }
        }

        System.out.println(sb);
    }

}