[백준 알고리즘] - 숫자 카드 2 (10816번) with Python

📎 간략한 문제 정리

• 개수가 (1 ≤ N ≤ 500,000)인 숫자 배열 N이 주어집니다. 각 숫자의 범위는 -10,000,000보다 크거나 같고, 10,000,000보다 작거나 같습니다. 그 후 새로운 숫자 배열 M을 입력 받는데, M의 숫자들이 N의 배열에서 몇번 나오는지 출력하는 문제입니다.

📈 문제 분석

• 문제 카테고리는 이분탐색입니다. 배열 N의 정보를 어떻게 처리할지가 중요합니다.

🙋‍♂️ 내가 처음 생각한 해결 방법

• Counterdict를 활용해서 배열 N을 정리하면 O(N)으로 처리 가능할 것 같습니다.

💻 풀이한 코드

from sys import stdin
from collections import Counter
input = stdin.readline
N = int(input())
N_dict = Counter(list(map(int, input().split())))
M = int(input())
count = [0 for _ in range(M)]
M_list = list(map(int, input().split()))
for i in range(len(M_list)):
    if M_list[i] in N_dict:
        count[i] = N_dict[M_list[i]]
print(' '.join(map(str, count)))

📝 해결 과정에서 만난 문제, 고민들

• 이분 탐색: 문제의 섹션이 이분 탐색이기 때문에 이분 탐색을 활용한 방법을 생각해봤습니다. 이분 탐색의 조건은 다음과 같습니다.

  1. 원소의 정렬 여부
  2. 원소에 Random Access 가능 여부

  우선 원소가 오름차순이나 내림차순으로 정렬되어 있어야 대소 비교에 따른 검색 방향 설정이 가능하기 때문에 정렬이 필수입니다. 그리고 원소에 Random Access가 가능하다는 것은 예를 들어 Python의 list처럼 index만 알면 해당 자료에 O(1)로 접근 가능한지 여부입니다. 2번은 만족하지만 1번을 만족시키기 위해서는 최소 O(NlogN)의 Tim sort를 활용해야 합니다. 이분 탐색의 속도가 O(logN)이라고 하더라도 정렬 안된 배열에선 무의미합니다. 위의 코드에서 Counter 함수는 O(N)이고 for문 안에서 if 조건이 O(1)이므로 for문은 O(N)이 됩니다. 그래서 속도상 더 빠르다고 판단하여 위와 같이 구현했습니다.

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