파이썬 Python | 알고리즘 | 백준 숫자 카드 2

⭕ 파이썬 Python | 알고리즘 | 백준 숫자 카드 2

➡️ 문제링크

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

 

➡️ 문제 탐색하기

• 상근이가 가진 카드에서 특정 숫자들이 몇 개 있는지를 알아내야 한다.
• 카드의 개수(N)와 구해야 할 숫자의 개수(M)가 최대 500,000개까지 될 수 있다. 카드의 숫자 범위는 -10,000,000에서 10,000,000 사이이다.
• 각 숫자의 개수를 세는 방법은 각 쿼리마다 O(N)의 시간 복잡도를 가지며, M개의 쿼리에서 총 시간 복잡도가 O(M*N)으로 시간 초과가 발생한다.
• 카드 리스트를 정렬한 후, bisect_left와 bisect_right를 활용하여 각 숫자의 개수를 효율적으로 찾을 수 있다.
  • 카드 리스트 정렬: O(N log N)
  • 각 쿼리 처리: O(M log N)
  • 총 시간 복잡도는 O(N log N + M log N)으로, 대량의 데이터에서도 상대적으로 효율적이다.

 

➡️ 코드 설계하기

• 카드 리스트(N개)와 쿼리 리스트(M개)를 입력받는다.
• 카드 리스트를 오름차순으로 정렬한다.
• bisect_left와 bisect_right를 활용하여 특정 숫자의 첫 번째 위치와 마지막 위치를 찾는다.
• 두 위치의 차이를 구하여 해당 숫자의 개수를 계산한다.

 

➡️ 시도 회차 수정 사항 (Optional)

1회 차 

• 시간 초과
• 처음에는 리스트의 count() 메서드를 사용하여 숫자의 개수를 세었으나, 데이터가 많아 시간 초과가 발생했다.

import sys

n = int(sys.stdin.readline())
cards = list(map(int, sys.stdin.readline().split()))

m = int(sys.stdin.readline())
queries = list(map(int, sys.stdin.readline().split()))

result = []

for query in queries:
    result.append(cards.count(query))

print(' '.join(map(str, result)))

---

2회 차

• 시간 752ms
• bisect_left와 bisect_right는 각각 O(log N)의 시간 복잡도로 특정 숫자의 첫 번째와 마지막 위치를 찾는 데 사용된다.

import sys
from bisect import bisect_left, bisect_right

n = int(sys.stdin.readline().strip())
cards = list(map(int, sys.stdin.readline().strip().split()))

m = int(sys.stdin.readline().strip())
queries = list(map(int, sys.stdin.readline().strip().split()))

cards.sort()

result = []
for query in queries:
    left_index = bisect_left(cards, query)
    right_index = bisect_right(cards, query)
    count = right_index - left_index
    result.append(count)

print(' '.join(map(str, result)))

 

 

➡️ 정답 코드

import sys
from bisect import bisect_left, bisect_right

n = int(sys.stdin.readline().strip())
cards = list(map(int, sys.stdin.readline().strip().split()))

m = int(sys.stdin.readline().strip())
queries = list(map(int, sys.stdin.readline().strip().split()))

cards.sort()

result = []
for query in queries:
    left_index = bisect_left(cards, query)
    right_index = bisect_right(cards, query)
    count = right_index - left_index
    result.append(count)

print(' '.join(map(str, result)))