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

 

정답 코드 및 풀이는 맨 아래에 있습니다.

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

 

• 쉬운 이분 탐색 문제였다.

---

< 수 찾기 > 

[문제]

N개의 정수 A[1], A[2], …, A[N]이 주어져 있을 때, 이 안에 X라는 정수가 존재하는지 알아내는 프로그램을 작성하시오.

[입력]

첫째 줄에 자연수 N(1 ≤ N ≤ 100,000)이 주어진다. 다음 줄에는 N개의 정수 A[1], A[2], …, A[N]이 주어진다. 다음 줄에는 M(1 ≤ M ≤ 100,000)이 주어진다. 다음 줄에는 M개의 수들이 주어지는데, 이 수들이 A안에 존재하는지 알아내면 된다. 모든 정수의 범위는 -2^31 보다 크거나 같고 2^31보다 작다.

[출력]

M개의 줄에 답을 출력한다. 존재하면 1을, 존재하지 않으면 0을 출력한다.

예제 입력	예제 출력
5 4 1 5 2 3 5 1 3 7 9 5	1 1 0 0 1

---

아이디어

시간복잡도가 O(N)인 일반적인 탐색을 이용한다면 M이 최대 10만일 때, 최대 10만 번의 연산을 하므로 어림잡아 100번의 연산을 해야 하므로 시간초과가 날 수밖에 없다. 따라서 시간복잡도가 O(logN)인 이분 탐색을 이용하여 연산을 해 주어야 한다. M이 10만일 때, log(10만) 번의 연산을 하므로 대충 60만 번의 연산을 한다고 가정하면 충분히 통과될 수 있다.

풀이 및 코드

n = int(input())
array = list(map(int, input().split()))
array.sort()
m = int(input())
targetArray = list(map(int, input().split()))

# 이분 탐색
def binarySearch(array, target):
  start = 0
  end = len(array) - 1
  while (start <= end):
    mid = (start + end) // 2
    # target이 있다면 그 즉시 return 1
    if array[mid] == target:
      return 1
    elif array[mid] < target:
      start = mid + 1
    else :
      end = mid - 1
  # while문을 다 돌렸는데 없다면 return 0
  return 0

for target in targetArray:
  print(binarySearch(array, target))

while문을 이용한 이분 탐색을 구현하였다.

후기

이 전에 이분탐색을 몰라서 한 번 포기한 적이 있었던 문제이다. 이렇게 쉬운 알고리즘을 왜 그냥 넘겼을까 하는 생각이 든다.