[BOJ_Python] 1920. 수 찾기

문제

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

 

사용 알고리즘

이분탐색, 해시 맵

https://www.acmicpc.net/blog/view/109

 

풀이

고려사항

1. target의 존재 여부

 - 이분 탐색으로 정렬 리스트 탐색을 통한 찾기

 - 해시 맵의 키를 통한 찾기

 

후기

1. 이 문제의 keypoint는 조건의 수 범위가 크다는 것이다.

리스트에 들어올 수 있는 정수의 범위는 -2^31보다 크거나 같고 2^31보다 작다.N과 M 역시 100,000으로 크기가 크기 때문에 하나하나 탐색하는 것은 시간 초과가 발생한다.

 

2. 이 문제를 두가지 방식으로 풀이했다.

2-1. 이분 탐색을 통한 풀이

인덱스를 기준으로 left와 right를 설정하고

그 가운데 값으로 기준을 삼아 이분탐색을 진행한다.

이때, 처음에 인덱스가 아닌 값을 기준으로 진행하였다가 오답이 나왔다.

이는 지금 값들이 연속으로 있지 않은데 이분탐색을 진행해서 생긴 오답이였다.

값이 연속으로 존재하지 않으면 인덱스를 기준으로 이분탐색을 진행하여야한다.

# 인덱스를 통한 이분탐색 기준 설정
left, right = 0, len(N_lst) - 1

# 값을 기준으로한 이분탐색 기준 설정
left, right = N_lst[0], N_lst[-1]

# 값을 기준으로 했을 때 반례
input 값
5
10 20 30 40 50
2
25 50

기대 답안
0
1

출력된 답안
1
1

 

 

2-2. 해시 맵을 통한 풀이

해시 맵에 숫자를 키로 설정하여 저장한 후 for문으로 해시 맵을 탐색하는 풀이이다.

 

3. 시간복잡도 

3-1. 이분탐색의 경우 

정렬 :  O(Nlog⁡N)

M_lst에 대한 이분탐색 : M⋅O(logN)

전체 : O(NlogN+MlogN)

3-2. 해시 맴의 경우

딕셔너리 생성 : O(N)

존재여부 확인 : O(M)

전체 : O(N+M)

3-3. 결론

공간복잡도보다 시간복잡도가 더 중요한 문제의 경우 해시를 통한 탐색이 더 유리하다.

하지만, 공간복잡도를 더 중심적으로 고려해야한다면 이분탐색이 더 좋은 선택이 될 수 있다.

이문제의 경우 공간복잡도보다 시간복잡도를 더 고려해야하므로 해시가 더 좋은 선택이 될 수 있다.

 

코드

이분탐색 코드

import sys
input = sys.stdin.readline


def binary(target):

    left, right = 0, len(N_lst) - 1

    while left <= right:
        mid = (left + right) // 2
        if target < N_lst[mid]:
            right = mid - 1
        elif target == N_lst[mid]:
            print(1)
            return True
        else:
            left = mid + 1
    print(0)
    return False


N = int(input())
N_lst = list(map(int, input().split()))

M = int(input())
M_lst = list(map(int, input().split()))

N_lst.sort()

for target in M_lst:
    binary(target)

 

해시 맵 코드

import sys
input = sys.stdin.readline

N = int(input())
N_lst = list(map(int, input().split()))

M = int(input())
M_lst = list(map(int, input().split()))

num_dic = {}
for number in N_lst:
    num_dic[number] = num_dic.get(number, 0) + 1
    
for i in M_lst:
    if i in num_dic:
        print(1)
    else:
        print(0)

 

결과

위 결과 : 이분탐색 코드

아래 결과 : 해시 맵 코드