[Python] 백준 - 1920문제 풀이(수 찾기)

문제 링크

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

아이디어

이번 문제는 시간복잡도를 줄이며 두번째 숫자 모음에 있는 숫자들이 첫번 째 숫자 모음에 있는지 탐색하는 문제라는 생각이 들었습니다.

 

어떻게 시간복잡도를 줄일지 생각하다가, 처음에는 이진 탐색이 생각 났습니다. 그런데 이것은 정렬이 선행되어야 했고, 정렬의 평균적 시간 복잡도는 O(nlogn)이기 때문에 좀 더 빠른 방법이 없을지 고민해 봤습니다.

 

그러다가 배열을 set함수를 사용해 집합으로 바꿔 평균 O(n)시간복잡도로 중복을 제거하고, 평균 O(1) 시간복잡도로 탐색하면 더 빠를 거 같아 set함수를 이용한 탐색을 사용하기로 결정했습니다.

 

문제 해결의 아이디어는

1. 두번째 줄의 숫자들을 arr배열에 저장해둡니다.

2. 중복을 제거하기 위해 평균적으로 O(n)의 시간복잡도로 중복을 제거하는 set함수를 사용하여 집합을 만듭니다.

3. 그 후 네번째 줄의 숫자들을 arr2배열에 저장해둡니다.

4. arr2 배열의 요소들을 순차적으로 반복문을 돌리며 집합에 숫자가 있으면 1을 출력하고 없다면 0을 출력합니다.

였습니다.

 

이를 코드로 구현하면

집합 소스코드

n = int(input())
arr = list(input().split())

m = int(input())
arr2 = list(input().split())

set1 = set(arr)

for x in arr2:
    if x in set1:
        print(1)
    else:
        print(0)

이렇습니다.

 

이진 탐색으로도 가능 할 것 같아서 시도를 해봤습니다.

파이썬에서 1초면 20,000,000의 연산을 하고 정렬은 O(NlogN) 데이터 갯수는 100,000 그래서 log2(100,000)이 17정도 나오는 것을 참고하여 1,700,000 정도 사용하고, 이진 탐색은 O(logN)이기 때문에 한 요소마다 17번안에 찾을 수 있다는 판단이 되었고, M의 데이터 갯수도 100,000개니 1,700,000 + 1,700,000 해서 3,400,000 정도 연산을 할 것이라는 계산이 나왔고, 2천만번보다는 작기 때문에 제출해봤습니다.

이진탐색 소스코드

def binary_search(target, data):
    start = 0
    end = len(data) - 1

    while start <= end:
        mid = (start + end) // 2

        if data[mid] == target:
            return 1
        elif data[mid] > target:
            end = mid -1
        else:
            start = mid + 1
    return 0

n = int(input())
arr = list(map(int, input().split()))
arr.sort()

m = int(input())
arr2 = list(map(int, input().split()))


for x in arr2:
    if binary_search(x, arr):
        print(1)
    else:
        print(0)

 

제출했더니 통과가 되었습니다. 이렇게 두 가지 방법을 생각하여 문제를 풀어보았습니다.

 

배운 점

유튜브에서 set으로 중복제거하는 시간복잡도가 평균적으로는 O(n)이지만, 최악의 경우 O(n^2)이 나온다해서 어떻게 해서 저런 시간 복잡도가 나오는지 확인해본 결과, set은 해시 테이블을 사용한다고 합니다.

해시 테이블은 키(key)와 값(value)를 쌍으로 저장하는 데이터 구조입니다.

 

주로 해시함수(hash function)와 버킷(bucket)이라는 개념으로 동작하는데,

해시함수는 주어진 키를 특정 숫자(index)로 매핑하는 역할을 하고 index는 bucket의 위치를 가르킵니다.

예를 들어 키"apple"은 해시함수를 통해 숫자(index) 312957017230123 등의 값으로 변환되고 312957017230123 위치에 있는 bucket에 저장합니다.

 

여기서 "apple"의 해시도 123이고 "banana"의 해시도 123이면 어떨까요? bucket은 하나인데 두개의 키를 저장해야하는 경우가 생깁니다. 이것을 해시 충돌이라고 합니다.

 

해시 충돌을 해결하는 방법은 체이닝(chaning)과 오픈 어드레싱(Open Addressing)방식이 있습니다.

 

체이닝은 "apple"이 먼저 들어가있다면 연결리스트로 "banana"를 뒤에 달아놓는 방법으로 같은 bucket에 저장하는 방식입니다.

오픈 어드레싱은 123 버킷이 차있으니 124, 125에 빈 버킷이 있나 순차적으로 확인하고 빈 버킷에 삽입하는 방식입니다.  

 

여기서 최악의 시간 복잡도를 가지는 경우는 모든 키가 동일한 해시 값을 가지는 경우입니다.

문제의 예시를 들면

하나의 bucket에 모든 키가 들어가게 되면 그 요소를 찾는데에 O(N)시간이 걸리게 되고, 그것을 M번 반복해야 하니 O(NM) 시간이 걸립니다.

 

최악의 경우는 품질이 나쁜 해시 함수를 사용하거나 해시함수의 공간을 충분히 확보하지 않았을 때 나타난다고 합니다.