[백준] 1920번 파이썬 (수 찾기)

1. 문제와 예제

문제

예제

특정 수가 리스트에 있는지 찾는 것이므로 탐색 방법 중 하나를 쓰면 되겠다.

---

2. 코드

1) 이분 탐색 사용

# 이분 탐색 사용
# 입력 받기
N = int(input())
A = list(map(int, input().split()))
M = int(input())
X_lst = list(map(int, input().split()))

# 이분탐색을 위해 리스트 정렬
A.sort()

for X in X_lst:
    l, r = 0, N-1 # left, right 지점을 선택
    isExist = False

    # 이분탐색 시작
    while l <= r:
        m = (l + r) // 2 # 중간 지점을 mid로 선택
        if X > A[m]: # X가 mid보다 오른쪽에 있다면
            l = m + 1 # left 지점을 현재 mid 지점으로 이동
        elif X < A[m]: # X가 mid보다 왼쪽에 있다면
            r = m - 1 # right 지점을 현재 mid 지점으로 이동
        else: # X가 mid 지점 숫자라면
            isExist = True # X가 A 안에 존재함을 의미
            print(1)
            break

    if not isExist: # X가 A 안에 존재하지 않았을 경우
        print(0)

문제에서 의도한 방법이다. 사실 나는 두 번째 방법을 더 먼저 떠올렸다.

 

2) set 사용

# set 사용
# 입력 받기
N = int(input())
A = set(map(int, input().split()))
M = int(input())
X_lst = list(map(int, input().split()))

for X in X_lst:
    if X in A:
        print(1)
    else:
        print(0)

A를 list 대신 set 형태로 사용하는 방법이다. A 안에 X가 있는지만 확인하면 되기 때문에 A의 요소들 중 중복되는 것은 하나만 남겨도 된다는 것에서 나온 아이디어다.

---

3. 풀이

우선 가장 먼저 떠올리는 방법은 A를 list 형태로 하고 'if X in A'로 찾는 방법일 것이다. 하지만 N의 최댓값이 100,000이고 M의 최댓값이 100,000이며, 우리는 M개의 주어진 숫자들에 대해 각각 해당 숫자가 길이가 N인 A 안에 있는지 확인을 해야 한다. 따라서 최악의 경우 100,000 * 100,000 = 100억 정도의 연산을 해야 하는 것을 알 수 있다. 백준에서는 1억 번 연산하는 데 1초가 걸리므로 해당 방식을 사용하면 무조건 시간 초과 오류가 발생함을 예상할 수 있다.

대충 계산하면 위와 같은데, 사실 시간복잡도로 계산하는 게 더 좋다. 리스트의 in 연산자를 통한 포함 여부의 시간 복잡도는 O(N)이다.

 

이분탐색의 시간 복잡도는 O(logN)이다. N 최댓값 100,000의 logN이면 5이므로 충분히 시간 제한 안에 가능하다. (실제 소요 시간 : 620ms) 

 

또한 set과 dictionary의 in 연산을 통한 포함 여부 확인의 시간 복잡도는 O(1)이다. 따라서 당연히 시간 제한 안에 가능하며 실제로 백준에서 소요 시간을 비교해도 이분탐색 방법보다도 빠르다는 것을 확인할 수 있다. (실제 소요 시간 : 180ms)