[백준] 1920번: 수 찾기

문제

문제 바로가기 : https://www.acmicpc.net/problem/1920

해당 문제를 단순히 이진 탐색을 활용하여 해결하였으나 시간 복잡도 측면에서 더 좋은 방법이 있어서 정리해보았습니다. 풀이 2~4는 유튜브 영상풀이를 참고하였습니다.

풀이1: 이진탐색 활용

이 문제는 이진 탐색(Binary Search) 알고리즘을 이용하여 해결할 수 있습니다.

이진 탐색 : 정렬되어있는 데이터에서 특정한 값을 찾아내는 알고리즘

우선 입력받는 코드부터 작성해봅시다.

N = int(input())
arrN = list(map(int, input().split()))
arrN.sort()
M = int(input())
arrM = list(map(int, input().split()))

N과 M을 입력받고 각각 N, M개의 수를 받아 리스트를 생성합니다.

이후 이진 탐색을 위한 함수 bin_search()를 정의합니다.

def bin_search(a, key):
  lo = 0    # 검색범위 맨 앞 원소의 인덱스
  hi = len(arrN) - 1    # 검색범위 맨 뒤 원소의 인덱스

  while True:
    mid = (lo + hi) // 2    # 중앙 원소의 인덱스
    if arrN[mid] == arrM[i]:
      return mid
    elif arrN[cursor] < arrM[i]:
      lo = mid + 1
    else:
      hi = lo - 1
    if lo > hi:
      break
  return -1

arrM 리스트를 반복해서 돌면서 각 원소를 키 값으로 설정하여 그 키 값이 arrN리스트에 있는지 탐색합니다.

for i in range(M):
  ky = arrM[i]  # 검색할 키 값 ky
  idx = bin_search(arrN, ky)
  if idx == -1:
    print(0)
  else:
    print(1)

풀이 2: lower_bound()

이번에는 Lower Bound의 개념을 이용하여 문제를 풀어봅시다.
- 참고 : Lower Bound와 Upper Bound

def lower_bound(arr, val):
  lo = 0
  hi = len(arr) 
  while lo < hi:
    mid = (lo + hi)//2
    if arr[mid] < val:
      lo = mid+1
    else:
      hi = mid  
  return lo  

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

for x in qry:
  idx = lower_bound(arr, x)
  if idx < n and arr[idx] == x:
    print(1)
  else:
    print(0)

풀이 3: bisect_left()

lower bound 함수를 구현하지 않고 더 간단히 푸는 방법입니다. 파이썬은 자체적으로 bisect 라이브러리를 지원하는데 여기서 bisect_left와 bisect_right는 각각 lower bound와 upper bound에 해당됩니다.

from bisect import bisect_left

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

for x in qry:
  idx = bisect_left(arr, x)
  if idx < n and arr[idx] == x:
    print(1)
  else:
    print(0)

풀이 4: set 자료구조 활용

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

# set자료구조 -> 해쉬 set
# 특정 원소를 O(1)에 찾음

for x in qry:
  if x in arr:
    print(1)
  else:
    print(0)

참고자료

https://www.youtube.com/results?search_query=%EB%B0%B1%EC%A4%80+1920
https://iamzieun.tistory.com/12