Algorithm/이것이 코딩 테스트다/이진 탐색/부품 찾기

yellow·2021년 5월 22일

알고리즘 문제

목록 보기

14/58

📖문제

동빈이네 전자 매장에는 부품이 N개 있다. 각 부품은 정수 형태의 고유한 번호가 있다. 어느 날 손님이 M개 종류의 부품을 대량으로 구매하겠다며 당일 날 견적서를 요청했다. 동빈이는 때를 놓치지 않고 손님이 문의한 부품 M개 종류를 모두 확인해서 견적서를 작성해야 한다. 이때 가게 안에 부품이 모두 있는지 확인하는 프로그램을 작성해보자.
이때 손님이 요청한 부품 번호의 순서대로 부품을 확인해 부품이 있으면 yes를, 없으면 no를 출력한다. 구분은 공백으로 한다.

입력 조건

첫째 줄에 정수 N이 주어진다. (1 <= N <= 1,000,000)

둘째 줄에는 공백으로 구분하여 N개의 정수가 주어진다. 이때 정수는 1보다 크고 1,000,000 이하이다.

셋째 줄에는 정수 M이 주어진다. (1 <= M <= 100,000)

넷째 줄에는 공백으로 구분하여 M개의 정수가 주어진다. 이때 정수는 1보다 크고 1,000,000 이하이다.

출력 조건

첫째 줄에 공백으로 구분하여 각 부품이 존재하면 yes를, 없으면 no를 출력한다.

📝풀이과정

N개의 부품 중에서 M개의 부품을 찾으려고 할 때 순차탐색을 이용한다면 시간복잡도가 O(NM)이기 때문에 최악의 경우에는 시간초과가 난다.
반면에 이진탐색을 이용한다면 시간복잡도가 O(MlogN)이기 때문에 이진탐색을 사용하였다.

아무래도 이번 챕터가 이진 탐색을 다루는 중이었기 때문에 제일 먼저 이진 탐색을 생각해서 문제를 풀었지만, 책에서는 계수 정렬을 이용한 풀이, 집합 자료형을 이용한 풀이도 수록되어 있었다. 따라서 추가적으로 계수 정렬과 집합 자료형으로도 문제를 풀어보았다.

계수 정렬
매장에 있는 부품들의 번호를 기준으로 계수 정렬을 수행한다.
이 문제의 메모리 제한은 128MB인데 부품들의 번호의 범위는 1 초과 1,000,000 이하(-> 데이터 크기: 4MB)이기 때문에 계수 정렬을 사용하는 데 메모리는 충분하다.
부품들의 번호를 인덱스로 부품의 존재 여부를 확인할 수 있다.
집합 자료형
매장에 있는 부품들의 번호를 집합 자료형에 담아서 in 연산자를 통해 부품의 존재 여부를 확인할 수 있다.

⌨코드1 (이진 탐색)

import sys

# n과 매장에 있는 부품 입력받기
n = int(sys.stdin.readline().rstrip())
part = list(map(int, sys.stdin.readline().rstrip().split()))

# m과 손님이 문의한 부품 입력받기
m = int(sys.stdin.readline().rstrip())
find_part = list(map(int, sys.stdin.readline().rstrip().split()))

# 손님이 문의한 부품이 있는지 찾는 함수 (이진 탐색 이용)
def search_part(start, end, target):
  while start <= end:
    mid = (start + end) // 2
    
    if part[mid] == target:
      # 부품이 있는 경우 'yes' 출력
      print('yes', end = ' ')
      return
    elif part[mid] < target:
      start = mid + 1
    else:
      end = mid - 1
  # 부품이 없는 경우 'no' 출력
  print('no', end = ' ')

# 이진탐색을 진행하기 위해 리스트를 정렬
part.sort()
# 손님이 문의한 부품 각각 찾기
for i in range(m):
  search_part(0, n - 1, find_part[i])

⌨코드2 (계수 정렬)

import sys

# 계수 정렬을 위한 리스트
count = [0] * 1000001

# n과 매장에 있는 부품 입력받기
n = int(sys.stdin.readline().rstrip())
part = list(map(int, sys.stdin.readline().rstrip().split()))
# 매장에 있는 부품들 count 리스트에 표시
for i in part:
  count[i] = 1

# m과 손님이 문의한 부품 입력받기
m = int(sys.stdin.readline().rstrip())
find_part = list(map(int, sys.stdin.readline().rstrip().split()))

# count 리스트에 손님이 문의한 부품이 존재하는지 확인
for item in find_part:
  if count[item] == 1:
    print('yes', end = ' ')
  else:
    print('no', end = ' ')

⌨코드3 (집합 자료형)

import sys

# n을 입력받고 매장에 있는 부품 입력받아서 집합 자료형으로 구성하기
n = int(sys.stdin.readline().rstrip())
part = set(map(int, sys.stdin.readline().rstrip().split()))

# m과 손님이 문의한 부품 입력받기
m = int(sys.stdin.readline().rstrip())
find_part = list(map(int, sys.stdin.readline().rstrip().split()))

# 손님이 문의한 부품이 매장에 있는지 확인
for item in find_part:
  if item in part:
    print('yes', end = ' ')
  else:
    print('no', end = ' ')

💡 새로 알게된 점

None

값이 존재하는 변수에 대입해서 해당 변수에 아무런 값이 없다는 것을 표시할 때 사용한다.

입력 받음과 동시에 for문 돌리는 방법

이 방법을 몰랐던 내가 쓴 코드
-> 공백을 기준으로 받아온 데이터들로 리스트를 만들어서 리스트 순회
part = list(map(int, sys.stdin.readline().rstrip().split()))
for i in part:
  count[i] = 1
입력 받으면서 for문 돌리는 코드
for i in sys.stdin.readline().rstrip().split():
  count[int(i)] = 1
혹은
for i in map(int, sys.stdin.readline().rstrip().split()):
  count[i] = 1