[python/백준] 1920. 수찾기(S4)

📌 문제 탐색하기

👉 문제바로가기

*해당 문제에 대한 더 다양한 풀이는 여기를 참고하세요.

A의 배열에는 N개의 요소가 존재합니다. 또다른 정수들이 M개 주어지는데 이 정수들이 각각 A의 배열 어딘가에 존재하는지 아닌지를 판단하는 문제입니다.

M개의 정수를 B의 배열에 넣고 B의 원소를 처음부터 끝까지 하나씩 가져오면서 A의 배열에 존재하는지 여부를 판단하면 되겠네요. A의 배열을 처음부터 끝까지 모두 탐색하게 되는 경우 비효율적일것 같아서 A를 정렬시키고 중간 값A[mid]을 가져와서 해당 값과 찾는 값이 같은지, 그렇지 않은지(크거나 같은지)를 봅니다. 같다면 존재하는 것이므로 바로 1을 출력하면 될 것입니다.

크거나 작을 경우에는 중간값인 mid를 조정하여 탐색할 범위를 반씩 줄여나가면, 필요없는 값들은 탐색하지 않아도 되겠네요. 그럼 A배열의 모든 값을 탐색하는 것보다 효율적인 방법일 것 같습니다.

📌 알고리즘 선택

A의 배열을 정렬 후 탐색 범위를 반으로 줄이면서 탐색하는 것이므로 이진 탐색(binary search)에 해당됩니다.

가능한 시간복잡도

이진 탐색을 한 번 수행하게되면 시간복잡도는 O(logN)입니다. B의 원소는 총 M개이고 B의 원소마다 이분 탐색을 하기때문에 총 시간복잡도는 O(MlogN)이 됩니다. N과 M의 최댓값으로 구해보면 약 1500000회의 연산이 이루어집니다.

📌 코드 설계하기

1. N, M, (N개의 원소를 가진)리스트A, (M개의 원소를 가진)리스트B를 각각 Input받습니다.
2. 리스트 A를 sort()를 사용해 정렬합니다.
3. 수가 존재하는지 확인하는 함수search()를 구현하여 리스트B의 원소 각각이 리스트A에 존재하는지 여부를 체크합니다.
4. search()에서 리스트A에 해당 원소가 존재하면 1, 그렇지 않으면 0을 리턴하여 출력합니다.

📌 정답 코드

import sys

# 수가 존재하는지 확인하는 함수
def search(array, target, start, end):
  while start <= end:
    mid = (start + end) // 2
    if array[mid] == target:
      return 1
    elif array[mid] > target:
      end = mid - 1
    else:
      start = mid + 1
      
  return 0


N = int(sys.stdin.readline())
A = (list(map(int, sys.stdin.readline().split())))
M = int(sys.stdin.readline())
B = (list(map(int, sys.stdin.readline().split())))

A.sort()

for i in range(M):
  result = search(A, B[i], 0, N - 1)
  print(result)