1920: 수 찾기 - Python

문제

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

풀이 1 (오답 - 시간초과)

N = int(input())
A = list(map(int, input().split()))
M = int(input())
arr = list(map(int, input().split()))

for i in arr:
    print(1 if i in A else 0)

• 시간 초과가 발생했다.
• in 연산을 사용해 매번 전체를 탐색하기 때문에 시간이 오래 걸린다.
• 효율적인 탐색 방법을 사용하자.
  -> Binary Search를 이용하자.

풀이 2 (bisect 사용)

import bisect

N = int(input())
A = sorted(list(map(int, input().split())))
M = int(input())
arr = list(map(int, input().split()))

for i in arr:
    idx = bisect.bisect_left(A, i)
    if idx < len(A) and A[idx] == i: print(1)
    else: print(0)

• 이진탐색을 도와주는 bisect 모듈을 사용해보았다.
• bisect_left(arr, num): 정렬된 arr에 대해, 값 num을 삽입했을 때 정렬 순서를 유지할 수 있는 가장 왼쪽 인덱스르 반환
• 예시) arr = [1, 2, 3, 4, 5]에 대해
  • num = 2 -> bisect_left(arr, num) = 1
  • num = 4 -> bisect_left(arr, num) = 3

풀이 3 (set 사용)

N = int(input())
A = set(map(int, input().split()))
M = int(input())
arr = list(map(int, input().split()))

for i in arr:
    print(1 if i in A else 0)

• 이 글을 참고하였다.
• 풀이 1에서 A만 set로 변경해주었다.
• list의 in 연산 (membership tesing)의 평균 시간 복잡도는 O(n)이다.
  list는 단순 원소 나열 구조로, 추가적인 메모리 사용 없이 선형적으로 탐색한다.
• set의 in 연산의 평균 시간 복잡도는 O(1)이다.
  이는 set가 Hash Table 기반으로 구현돼있기 때문이다.
  다만 Hash Table을 유지하고 관리하는데 추가 메모리가 필요하다.

---

오늘의 교훈

• bisect 모듈은 이진 탐색 구현을 도와준다.
  더 정확하게는, 정렬된 list에 element를 삽입할 때, list가 정렬된 순서를 유지하도록 한다.
• bisect의 사용 예제는 다음과 같다. (출처: GPT o1)

import bisect

lst = [1, 2, 4, 5, 7, 10] # list는 반드시 정렬돼있어야 한다!!

pos_left = bisect.bisect_left(lst, 3)
print("bisect_left:", pos_left)  # bisect_left: 2

pos_right = bisect.bisect_right(lst, 5)
print("bisect_right:", pos_right)  # bisect_right: 4

pos = bisect.bisect(lst, 5)
print("bisect:", pos)  # bisect: 4

bisect.insort_left(lst, 3)
print("insort_left:", lst)  # insort_left: [1, 2, 3, 4, 5, 7, 10]

bisect.insort_right(lst, 5)
print("insort_right:", lst)  # insort_right: [1, 2, 3, 4, 5, 5, 7, 10]

참고 자료

• TimeComplexity
• 5. Data Structures