[BOJ](Python) 백준 1920번: 수 찾기

문제

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

1920번: 수 찾기

주제	해시 테이블
시간 / 메모리 제한	1초 / 128MB
정답 비율	29.789%

N개의 정수 A[1], A[2], ... , A[N]이 주어져 있을 때,

이 안에 X라는 정수가 존재하는지 알아내는 프로그램을 작성하시오.

입력

첫째 줄에 자연수 N(1 <= N <= 100,000)이 주어진다.

다음 줄에는 N개의 정수 A[1], A[2], ... , A[N]이 주어진다.

다음 줄에는 M(1 <= M <= 100,000)이 주어진다.

다음 줄에는 M개의 수들이 주어지는데, 이 수들이 A 안에 존재하는지 알아내면 된다.

• 모든 정수의 범위는 (-2)^31보다 크거나 같고 2^31보다 작다.

출력

M개의 줄에 답을 출력한다.

존재하면 1을, 존재하지 않으면 0을 출력한다.

- 예제 입력 1

5
4 1 5 2 3
5
1 3 7 9 5

- 예제 출력 1

1
1
0
0
1

 풀이

위 문제를 보고 바로 작성할 수 있는 코드를 적어 실행해 봤더니 역시나

아니나 다를까 시간초과가 발생하였다.

import sys

N = int(sys.stdin.readline())
given = list(map(int, sys.stdin.readline().split()))

M = int(sys.stdin.readline())
numbers = list(map(int, sys.stdin.readline().split()))

for num in numbers:
    if num in given:
        print('1')
    else:
        print('0')

위의 경우 numbers를 순회하며 O(N)의 연산을 수행하고

in 연산에서 다시 O(N) 연산을 수행하기 때문에

총 O(N^2)의 연산이 사용되었고 이 경우 시간초과가 발생한다는 것을 알 수 있다.

 

1) 이진 탐색

저번 백준 문제 풀이에 사용한 이진 탐색 트리는 O(logN) 연산이므로

이를 사용한 코드를 작성해보았다.

import sys

def binary_search(list, target, start, end):
    if start > end:
        return 0
    mid = (start + end) // 2
    if list[mid] == target:
        return 1
    elif list[mid] > target:
        return binary_search(list, target, start, mid - 1)
    else:
        return binary_search(list, target, mid + 1, end)

N = int(sys.stdin.readline())
given = list(map(int, sys.stdin.readline().split()))

sorted_list = sorted(given)

M = int(sys.stdin.readline())
numbers = list(map(int, sys.stdin.readline().split()))

for num in numbers:
    print(binary_search(sorted_list, num, 0, len(sorted_list) - 1))

위와 같이 이진 탐색을 이용하여 풀이하니 시간 초과가 발생하지 않았다.

 

2) 해시테이블

이진 탐색을 이용한 풀이로 이미 정답은 맞추었지만

해시테이블을 이용한 풀이도 가능하다.

 

파이썬에서는 딕셔너리와 set 자료형을 이용하면 해시테이블을 사용할 수 있는데,

딕셔너리가 더욱 익숙하므로 딕셔너리를 이용해 해시테이블 코드를 작성해보았다.

 

딕셔너리는 해시 구조로 이루어져 있기 때문에

바로 해시테이블 알고리즘 풀이가 가능하다.

 

딕셔너리를 이용한 in 메서드는 O(1) 시간 복잡도이다.

리스트에서 in 메서드를 사용했을 때에는 O(N) 시간 복잡도이므로 훨씬 개선할 수 있다.

import sys

N = int(sys.stdin.readline())
given = list(map(int, sys.stdin.readline().split()))
given_dict = {}
for key in given:
    given_dict[key] = ' '
M = int(sys.stdin.readline())
numbers = list(map(int, sys.stdin.readline().split()))

for num in numbers:
    if num in given_dict:
        print('1')
    else:
        print('0')

위와 같이 코드를 작성해주었다.

딕셔너리의 value 영역은 낭비하고 key 영역만 사용하여 다소 비효율적이어 보일 수 있지만,

총 O(N) 연산으로 코드를 작성할 수 있다.

실제로 실행해 보았을 때 아래와 같은 결과를 확인할 수 있었다.

 

이진탐색을 이용한 풀이와 연산에 소요된 시간을 비교했을 때

약 3배 이상 빨리 수행된 것을 확인할 수 있다.

 

딕셔너리, 즉 해시 테이블 연산의 효율성을 눈으로 확인하였다.