[이.취.코] Chap 7. 이진 탐색 - 부품 찾기

1. 부품 찾기

• 난이도
  • 중하
• 풀이 시간
  • 30분
• 시간 제한
  • 1초
• 메모리 제한
  • 128MB

A. 문제

우리 매장에는 부품이 N개 있다. 각 부품은 정수 형태의 고유한 번호가 있다.

손님이 M개 종류의 부품을 대량으로 구매하겠다며 견적서를 요청한다.

손님이 문의한 부품 M개 종류를 모두 확인해서 견적서를 작성해야 한다.

이때, 가게 안에 부품이 모두 있는지 확인하는 프로그램을 작성하자.

a. 예를 들면.

N = 5
[8, 3, 7, 9, 2]

M = 3
[5, 7, 9]

이때, 손님이 요청한 부품 번호의 순서대로 부품을 확인해 부품이 있으면 yes, 없으면 no를 공백으로 구분하여 출력한다.

b. 입력 조건

• 첫째 줄에 정수 N이 주어진다.
  • 1 <= N <= 1,000,000
• 둘째 줄에는 공백으로 구분하여 N개의 정수가 주어진다.
  • 정수는 1보다 크고 1,000,000 이하이다.
• 셋째 줄에는 정수 M이 주어진다
  • 1 <= M <= 100,000
• 넷째 줄에는 공백으로 구분하여 M개의 정수가 주어진다.
  • 정수는 1보다 크고 1,000,000 이하이다.

c. 출력 조건

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

d. 테스트 케이스

• 입력 예시

  
  5
  8 3 7 9 2
  3
  5 7 9
  
  

• 출력 예시

  
  no yes yes
  
  

B. 내 답안

import sys  
  
n = int(input())  
my_part = list(map(int, sys.stdin.readline().rstrip().split()))  
  
m = int(input())  
customer_part = list(map(int, sys.stdin.readline().rstrip().split()))  
result = []  
  
for i in customer_part:  
    if i not in my_part:  
        result.append("no")  
    else:  
        result.append("yes")  
  
print(result)

a. 회고

잘한점

• 입력 조건(N의 범위가 100만)을 보고 어떤 알고리즘을 사용해야 하는지 판단하였다.
  • NlogN은 20 * 100만으로 2000만이라 파이썬 코드로 1초 정도 걸릴 것이라 생각하였다.
  • N이나 logN이 있지만, 방금 공부한 logN인 이진 탐색이 떠올랐다.
• sys 라이브러리를 사용한 것.
  • 정수의 개수가 N인데, N의 범위가 최대 100만이다. 그래서 대용량 입력 처리를 위해 sys 라이브러리를 사용해봤다.

반성

• 문제를 빨리 푸는데 집중하여 문제와 출력 조건을 제대로 읽지 않았다.
  • 둘째, 넷째 줄에 입력받는 숫자가 부품의 고유 번호라는 부분을 생략하고 생각하여, 만약 주문한 부품 수량이 재고 수량보다 많으면 어떻게 처리하지?라는 고민을 하며 문제를 풀었다.
  • 출력 조건으로 모든 부품이 존재하지 않으면 no 1개만 출력하는 것으로 이해했으나, 테스트 케이스와 내 답을 비교하며 그렇지 않다는 것을 알게 되었다.
• 이진 탐색 알고리즘을 떠올렸으나, in을 사용하여 문제를 해결하였다.
  • 내가 푼 답은 시간 복잡도가 O(N)으로 예상되기에 큰 문제는 없겠지만, 그래도 이진 탐색을 사용하여 문제를 해결했으면 하는 아쉬움이 있다.

C. 문제 해설

다량의 데이터 검색은 이진 탐색 알고리즘을 이용해 효과적으로 처리할 수 있다.

매장 내 N개의 부품을 번호를 기준으로 정렬하자. 이후 M개의 찾고자 하는 부품이 각각 매장에 존재하는지 검사하면 된다. 이때 매장의 부품들은 정렬이 되어 있기 때문에 이진 탐색을 수행하여 찾을 수 있다.

부품을 찾는 과정에서 최악의 경우 시간 복잡도 O(M * logN)이라 200만번의 연산이 이루어진다고 생각할 수 있다. N개의 부품을 정렬하는데 시간 복잡도 O(N * logN)이 최대 약 2,000만을 예상할 수 있다.

결과적으로 이진 탐색을 사용하는 문제 풀이 방법의 경우 시간 복잡도는 O((M + N) * logN)이다

이진 탐색 말고도 계수 정렬의 개념을 이용해 풀 수 있다. 모든 원소의 번호를 포함할 수 있는 크기의 리스트를 만든 뒤에, 리스트의 인덱스에 직접 접근하여 특정한 번호의 부품이 매장에 존재하는지 확인하면 된다.

단순히 특정한 수가 한 번이라도 등장했는지를 검사하면 되므로 집합 자료형을 이용해서 문제를 해결할 수 있다. 집합 자료형은 단순히 특정한 데이터가 존재하는지 검사할 때에 매우 효과적으로 사용할 수 있다.

어차피 부품 번호가 고유한데 집합을 사용하여 중복제거를 해줄 필요가 있을까?

a. 책 답안

• 이진 탐색

  python-for-coding-test/5.py at master · ndb796/python-for-coding-test (github.com)

• 계수 정렬

  python-for-coding-test/6.py at master · ndb796/python-for-coding-test (github.com)

• 집합 자료형

  python-for-coding-test/7.py at master · ndb796/python-for-coding-test (github.com)

참고문헌

나동빈, "이것이 취업을 위한 코딩 테스트다 with 파이썬", 초판, 2쇄, 한빛미디어, 2020년