[BOJ] 백준 1920번 - 수 찾기 (Python)

문제

문제 바로가기

해결

파이썬문법을 안다면 문제를 보자마자 1초만에 보고 2초만에 작성해서 제출이 가능한 문제였다.

정말 무지성으로 갈기게 될 경우 코드는 다음과 같다.

첫 번째 제출

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

for num in nums:
  if num in arr:
    print(1)
  else:
    print(0)

겁내 간단하다. 하지만 당연하게도 호락호락하지 않다. 100,000개에 달하는 정수가 있고, 그 정수는 각각 -2^31 ~ 2^31 의 괴랄한 범위를 가진다. 그럼 당연하게도 최대의 경우 200,000개에 달하는 매우 넓은 범위의 정수가 있을 거라는 생각을 해야 한다.

그렇다. 정렬과 탐색에서 시간과 메모리를 아껴 써야하는 문제다.

정렬의 시간 복잡도
선택 정렬	O(N^2)
삽입 정렬	O(N^2)
퀵 정렬	O(NlogN)
정렬 라이브러리	O(NlogN)
계수 정렬	O(N+K)

기본 라이브러리 외 더 빠른 정렬은 계수정렬의 방법이 있는데, 이때 K는 데이터의 범위이지만, 데이터의 범위는 -2^31 ~ 2^31이므로 정렬은 기본 라이브러리를 사용해야 한다고 생각했다.

다음은 탐색이다.

당연히 이진 탐색을 먼저 생각했다.

결과는 정답.

정답 코드

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

arr.sort()

def binary_search(start, end, target, arr):
  if start > end:
    return 0
  mid = (start + end) // 2
  if arr[mid] == target:
    return 1
  elif arr[mid] > target:
    return binary_search(start, mid - 1, target, arr)
  else:
    return binary_search(mid + 1, end, target, arr)
  
for num in nums:
  print(binary_search(0, len(arr) - 1, num, arr))

재귀가 아닌 일반 while 반복문으로 작성한 이진 탐색 코드는 다음과 같다.

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

arr.sort()

def binary_search(start, end, target, arr):
  while start <= end:
    mid = (start + end) // 2
    if arr[mid] == target:
      return 1
    elif arr[mid] > target:
      end = mid - 1
    else:
      start = mid + 1
  return 0
  
for num in nums:
  print(binary_search(0, len(arr) - 1, num, arr))