[Boj 1920] 수 찾기

📎 문제링크

1. 시간복잡도

N(1 ≤ N ≤ 100,000), M(1 ≤ M ≤ 100,000) 범위이므로, 이중for를 돌리게 되면 시간초과가 된다.

이분탐색을 으로 시간초과를 피할 수 있다.

2. 풀이

2.1 범위체크

모든 정수의 범위는 $-2^{31}$ 보다 크거나 같고 $2^{31}$보다 작다. ➡️ int형의 범위

2.2 left, right 갱신 주의

양 끝점을 단순히 mid로 갱신을 해주면 무한루프에 빠질 수 있다.
if (target[mid] == ele[i]) 조건을 통해 mid는 답이 될 수 없음을 확인 하였으므로 left, right 갱신시에 left = mid+1; right = mid-1; 와 같이 한 칸씩 추가로 이동을 해주어 범위를 좁혀 나가야 한다.

3. 코드

package week10;

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

public class Boj_1920 {
    static int N, M;
    static int[] target, ele, answer;
    public static void main(String[] args) throws Exception{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringBuilder sb = new StringBuilder();
        N = Integer.parseInt(br.readLine());
        target = Arrays.stream(br.readLine().split(" ")).mapToInt(Integer::parseInt).toArray();
        M = Integer.parseInt(br.readLine());
        ele = Arrays.stream(br.readLine().split(" ")).mapToInt(Integer::parseInt).toArray();

        Arrays.sort(target);

        int left, right, mid, result;
        for (int i = 0; i < ele.length; i++) {
            left = 0;
            right = target.length-1;
            result = 0;

            while (left <= right) {
                mid = (left+right)/2;

                if (target[mid] == ele[i]) {
                    result = 1;
                    break;
                }

                if (target[mid] < ele[i]) {
                    left = mid+1;
                } else {
                    right = mid-1;
                }
            }
            sb.append(result + "\n");
        }

        System.out.println(sb.toString());

    }
}