[1920] 수 찾기

✔ 수 찾기

[백준 1920]

문제 분석하기

N의 범위가 100000이므로 단순 반복문으로는 문제를 풀 수 없음

이진 탐색을 적용하면 O(MlogN) 시간 복잡도로 해결할 수 있으며, 자바의 기본 정렬을 사용하더라도 O(NlogN) 시간 복잡도를 가짐

손으로 풀어보기

1. 탐색 데이터를 1차원 배열에 저장한 다음 저장된 배열을 정렬
2. X라는 정수가 존재하는지 이진 탐색을 사용해 확인

슈도코드 작성하기

N(정렬할 수 개수) M(탐색할 숫자의 개수)
A(정렬할 배열 선언하기)
for(N의 개수만큼 반복하기)
{ 
    A 배열 저장하기
}
A 배열 정렬하기
for(M의 개수만큼 반복하기) 
{
    target(찾아야 하는 수)
    start(시작 인덱스)
    end(종료 인덱스)
    while(시작 인덱스 <= 종료 인덱스) {
        midi(중간 인덱스)
        if(중앙값 > target) {
            종료 인덱스 = 중간 인덱스 - 1
        }
        else if(중앙값 < target) {
            시작 인덱스 = 중간 인덱스 + 1
        } else {
            찾았으므로 반복문 종료하기
        }
    }
    if(찾았음) 1 출력
    else 0 출력
}

코드 구현하기

/**
 * 1920) 수_찾기
 */
public class D029_1920 {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        // N(정렬할 수 개수)
        int N = sc.nextInt();
        // A(정렬할 배열 선언하기)
        int[] A = new int[N];
        for (int i = 0; i < N; i++) {
            // A 배열 저장하기
            A[i] = sc.nextInt();
        }
        // A 배열 정렬하기
        Arrays.sort(A);
        // M(탐색할 숫자의 개수)
        int M = sc.nextInt();
        for (int i = 0; i < M; i++) {
            boolean find = false;
            // target(찾아야 하는 수)
            int target = sc.nextInt();
            // start(시작 인덱스)
            int start = 0;
            // end(종료 인덱스)
            int end = A.length - 1;
            while (start <= end) {
                // midi(중간 인덱스)
                int midi = (start + end) / 2;
                int midV = A[midi];
                if (midV > target) {
                    end = midi - 1;
                } else if (midV < target) {
                    start = midi + 1;
                } else { // 찾았으므로 반복문 종료하기
                    find = true;
                    break;
                }
            }
            // if(찾았음) 1 출력
            if (find) {
                System.out.println(1);
            } else { // else 0 출력
                System.out.println(0);
            }
        }
    }
}