[백준] 수 찾기(1920)

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

N의 범위가 최대 100,000이므로 단순 반복문만으로 문제를 해결하려고 하면 $O(N^2)$이 되어 시간초과로 해결할 수 없으며, 못해도 $O(NlogN)$의 시간복잡도인 알고리즘으로 해결해야 한다.

따라서 시간 복잡도가 $O(logN)$을 자랑하는 이진 탐색을 통해 문제를 해결해야 한다.

이진 탐색은 데이터가 정렬되어 있는 상태에서 타겟(target) 데이터와 중앙값을 비교하여 탐색할 범위를 절반씩 줄이는 기법이다.

데이터가 오름차순으로 정렬되어 있다고 가정하면 알고리즘 실행 흐름은 다음과 같다.

1. 데이터셋의 중앙값 구하기

   mid_idx = (start + end) / 2
   mid_val = A[mid_idx]

2. 타켓(target) < 중앙값인 경우 중앙값을 기준으로 오른쪽 데이터셋 선택

   데이터셋에서 탐색해야할 시작 인덱스를 중앙값 + 1로 설정한다는 의미와 동일하다.

   if target > mid_val:
   	start_idx = mid_idx + 1

3. 타겟(target) > 중앙값인 경우 중앙값을 기준으로 왼쪽 데이터셋 선택

   데이터셋에서 탐색해야할 끝 인덱스를 중앙값 - 1로 설정한다는 의미와 동일하다.

   if target < mid_val:
   	end_idx = mid_idx - 1

4. 1 ~ 3을 계속 반복하다가 중앙값 == 타겟(target)인 경우 탐색 종료

Python

따라서 파이썬의 전체 소스코드는 아래와 같다.

import sys
input = sys.stdin.readline

N = int(input())
A = list(map(int, input().split()))
M = int(input())
Q = list(map(int, input().split()))

A.sort()

for target in Q:
    found = False
    start = 0
    end = N - 1

    while start <= end:
        mid_idx = int((start + end) / 2)
        mid_val = A[mid_idx]

        if target == mid_val:
            found = True
            break
        elif target > mid_val:
            start = mid_idx + 1
        elif target < mid_val:
            end = mid_idx - 1
    
    if found:
        print(1)
    else:
        print(0)

Java

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

public class P_1920 {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        int N = Integer.parseInt(br.readLine());
        int[] A = new int[N];

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

        Arrays.sort(A);

        int M = Integer.parseInt(br.readLine());
        st = new StringTokenizer(br.readLine());
        for (int i = 0; i < M; i++) {
            int target = Integer.parseInt(st.nextToken());

            int start = 0;
            int end = N - 1;

            boolean result = false;
            while (start <= end) {
                // 중앙값 업데이트를 위해 여기에 선언하는 위치 주의
                int mid = (start + end) / 2;

                // 배열에 있는 중앙값과 찾고자하는 target 값을 비교해야함
                if (A[mid] < target) {
                    start = mid + 1;
                } else if (A[mid] > target) {
                    end = mid - 1;
                } else {
                    result = true;
                    break;
                }
            }

            if (result) System.out.println(1);
            else System.out.println(0);
        }
    }
}

참고로 데이터가 정렬되어 있는 상태에서 사용할 수 있음으로 입력받은 데이터에 대해 정렬하는 것을 잊지말자.

그리고 while문의 탈출 조건의 start <= end이므로 중앙값인 mid 선언을 반복문 안에 넣어 업데이트 하는 것에 유념하자.

마지막으로 배열에 있는 중앙값인 A[mid]와 target 값인 target값을 비교하자.