[백준 1920] 수 찾기

1. 링크

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

2. 문제 설명

(1) 문제

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

 

(2) 입력

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

 

(3) 출력

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

 

3. 코드

#1920

import sys

def binarySearch(arr, start, end, target):
    if start > end:
        return False
    mid = (start + end) // 2

    if (arr[mid] == target):
        return True
    elif (arr[mid] > target):
        return binarySearch(arr, start, mid-1, target)
    else:
        return binarySearch(arr, mid+1, end, target)

#입력 받기
N = int(input())
N_list = sorted(list(map(int, sys.stdin.readline().split(" "))))
M = int(input())
M_list = list(map(int, sys.stdin.readline().split(" ")))

#Binary Search 사용
for i in M_list:
    result = binarySearch(N_list, 0, N-1, i)
    if result: 
        print(1)
    else: 
        print(0)

4. 설명

이전에 아무 생각없이 in을 사용했을 때는 시간 초과가 난 문제이다. 당시 코드는 다음과 같다

#1920

#입력 받기
N = int(input())
N_list = list(map(int, input().split(" ")))
M = int(input())
M_list = list(map(int, input().split(" ")))
result = []

#N_list에 값 유무 입력
for i in M_list:
    if i in N_list: 
        result.append(1)
    else: 
        result.append(0)

#결과 출력
for i in result:
    print(i)

위와 같은 코드의 경우 O(N)의 시간복잡도가 나타나는데, 시간제한이 1초이고 정수 범위가 매우 크며 정수 개수도 최대 10만 개이므로 시간 초과가 발생한다.

그렇기 때문에 O(logN)의 시간복잡도를 가진 이진 탐색 알고리즘을 사용한다.

이진 탐색 (Binary search) 개념 및 구현

이진 탐색 알고리즘은 반복문을 이용할 수도 있고, 재귀문을 이용할 수도 있는데 나는 재귀문으로 구현하였다. 또한 일반적인 이진 탐색의 경우 해당하는 값의 인덱스 값을 return하는데, 이 문제에서는 그럴 필요가 없으므로 해당 수를 찾으면 True를 return하도록 작성하였다.

 

5. 배운 점

예전에 알고리즘 수업 들을 때 배운 이진 탐색 알고리즘을 사용해볼 수 있었다! 사실 처음 문제를 봤을 때 이진 탐색의 원리는 기억나는데 구체적인 구현 방법을 잊어서 구글링을 조금 했는데, 다른 사람들의 여러 코드를 보면서 여러 구현 방법을 확인해볼 수 있었다. 다음에 이진 탐색을 사용할 때는 구글링 없이 온전히 내 힘으로 코드를 짜내고 싶다.