📌 문제 탐색하기
👉 문제바로가기
- N: 상근이가 가지고 있는 숫자카드의 갯수(1 ≤ N ≤ 500,000)
- card: 상근이가 가지고 있는 숫자카드의 리스트
- M: 정수의 갯수(1 ≤ M ≤ 500,000)
- integer: 정수 M개의 리스트
card와 integer리스트에 들어있는 원소의 범위는 -10,000,000보다 크거나 같고, 10,000,000보다 작거나 같습니다. integer의 원소가 card리스트에 몇개씩 있는지 출력해야하는데, integer의 원소에 해당되는 값 각각을 card에서 찾을 때 모두 탐색하는 것이 아닌 필요없는 범위를 거르면서 탐색하면 더 효율적이겠네요.
이진 탐색으로 해당 원소가 card리스트에 존재하는지 찾고 해당 원소의 갯수를 card리스트에 대해 count()를 사용하여 구하면 됩니다.
📌 알고리즘 선택
이진 탐색을 활용하면 단계가 진행될 때마다 점점 탐색의 범위가 줄어들게 된다는 장점이 있습니다. 여기서 주의할 점은 이진 탐색의 경우 기존 배열이 정렬되어있는 상태여야 하므로 sort()를 먼저 사용해야 합니다.
가능한 시간복잡도
이진 탐색의 시간복잡도는 O(logN)입니다. for문에서 M번만큼 반복 수행해야 하고, card 리스트의 요소 N개에 대해서도 모두 탐색이 필요하므로 총 시간복잡도는 O((M+N)logN)이 되겠네요. 그렇다면 최악의 경우 연산횟수는 (500000 + 500000)*log(500,000) = 1000000*log(5*100000)= 약 19,000,000회의 연산이 수행됩니다.
📌 코드 설계하기
- 숫자 카드의 갯수 N, 숫자 카드에 적혀있는 정수 리스트
card, 정수의 갯수 M, 정수 리스트integer를 Input받습니다. card를 정렬합니다.integer의 각 원소에 대해card에 존재하는지 이진 탐색을 활용하여 찾습니다.- 존재하는 경우
count()를 사용하여 해당 원소의 갯수를 출력하고, 존재하지 않는 경우 0을 출력합니다.
📌 시도 회차 수정 사항 (Optional)
1회차
for i in range(M):
exist = binary_search(card, integer[i], 0, N - 1)
if exist:
print(card.count(integer[i]), end=' ')
else:
print(0, end=' ')위 코드에서 print(card.count(integer[i]), end=' ')가 존재함으로써 for문이 M번 반복되는동안 반복적으로 count()가 호출됩니다. count()의 경우 반복적인 호출 시 시간복잡도가 좋지 않기 때문에 성능이 좋은 Counter클래스를 사용하도록 수정했습니다.
📌 정답 코드
import sys
from collections import Counter
def binary_search(array, target, start, end):
while start <= end:
mid = (start + end) // 2
if array[mid] == target:
return True
elif array[mid] < target:
start = mid + 1
elif array[mid] > target:
end = mid - 1
N = int(sys.stdin.readline()) #숫자카드의 갯수
card = list(map(int, sys.stdin.readline().split())) #숫자카드 리스트
M = int(sys.stdin.readline()) #입력받을 정수의 갯수
integer = list(map(int, sys.stdin.readline().split())) #정수 M개의 리스트
count = Counter(card) #card배열에서 각 원소의 갯수
card.sort()
for i in range(M):
exist = binary_search(card, integer[i], 0, N-1)
if exist == True:
print(count[integer[i]], end=' ')
else:
print(0, end=' ')
print()
