[코딩테스트 공부] 수 찾기

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

일단 문제부터 읽어봅시다

일단 조건부터 분석을 해보겠습니다.

우선 N의 범위와 시간 제한을 먼저 확인해보겠습니다. N, M은 각각 100000까지 허용이 되고 있으며, 시간 제한은 1초이므로 1억회의 연산 까지만 허용이 되는 상황입니다.

그러면 다음으로, 어떤 복잡도를 사용해야하는지 분석을 해보겠습니다. 문제를 분석해보면, N의 복잡도로는 절대 해결이 불가능 하다는 것을 깨닫게 되는데요, 그러면 다음 복잡도를 사용할 수 있을겁니다.

• O(N^2)
• O(N * logN)

그러나, 첫번째 후보인 N^2의 경우 100000 기준으로 1억을 넘기 때문에 사용이 불가능하고, 두번째 복잡도 후보인 O(N * logN)의 경우에는 사용이 가능합니다.

그리고 logN의 복잡도를 가지는 대표적인 탐색 방법이 이진 탐색(binary search) 방식이기 때문에, 정렬 후 이진 탐색을 하는 방식으로 문제 해결을 구성했습니다.

일단 코드부터 분석을 해볼까요

import sys

input = sys.stdin.readline

# 이진탐색 함수
def binary_search(search_data, target_list, start, end):
    if start > end:
        return -1
    
    mid = (start + end) // 2
    
    if search_data == target_list[mid]:
        return mid
    elif target_list[mid] > search_data:
        end = mid - 1
    else:
        start = mid + 1
        
    return binary_search(search_data, target_list, start, end)

# 입력 받기
N = int(input())
first_list = list(map(int, input().split()))
M = int(input())
second_list = list(map(int, input().split()))

target_list = sorted(first_list)

for number in second_list:
    if binary_search(number, target_list, 0, N - 1) != -1:
        print(1)
    else:
        print(0)

구현이 매우 간단한 모습을 확인할 수 있습니다.

이진 탐색을 경우 우선 탐색 대상의 배열이 정렬이 되어있어야한다는 점이 전제 조건이기 때문에, 먼저 리스트를 정렬하고 시작했습니다.

그 후에, 두 번째로 입력받은 리스트의 숫자를 순회하면서, 이진 탐색을 시행하면서 0 또는 1을 출력해주면 문제 해결은 끝입니다.