1. 문제
숫자 카드는 정수 하나가 적혀져 있는 카드이다. 상근이는 숫자 카드 N개를 가지고 있다. 정수 M개가 주어졌을 때, 이 수가 적혀있는 숫자 카드를 상근이가 몇 개 가지고 있는지 구하는 프로그램을 작성하시오.
2. 입력
첫째 줄에 상근이가 가지고 있는 숫자 카드의 개수 N(1 ≤ N ≤ 500,000)이 주어진다. 둘째 줄에는 숫자 카드에 적혀있는 정수가 주어진다. 숫자 카드에 적혀있는 수는 -10,000,000보다 크거나 같고, 10,000,000보다 작거나 같다.
셋째 줄에는 M(1 ≤ M ≤ 500,000)이 주어진다. 넷째 줄에는 상근이가 몇 개 가지고 있는 숫자 카드인지 구해야 할 M개의 정수가 주어지며, 이 수는 공백으로 구분되어져 있다. 이 수도 -10,000,000보다 크거나 같고, 10,000,000보다 작거나 같다.
3. 출력
첫째 줄에 입력으로 주어진 N개의 수에 대해서, 각 수가 적힌 숫자 카드를 상근이가 몇 개 가지고 있는지를 공백으로 구분해 출력한다.
4. 예제 입력 / 출력
10
6 3 2 10 10 10 -10 -10 7 3
8
10 9 -5 2 3 4 5 -10
3 0 0 1 2 0 0 2
5. 풀이 과정
처음에는 무턱대고 리스트의 count 함수를 사용했다.
n = int(input())
cards = list(map(int, input().split()))
m = int(input())
my_cards = list(map(int, input().split()))
for card in my_cards:
print(cards.count(card), end = ' ')물론 정상적으로는 작동했지만, 숫자 카드의 개수가 크다보니 실행 시간이 초과되었다. 실행 시간을 줄이기 위해 생각한 방법은 바로 이분 탐색이다.
import sys
# 찾는 값의 가장 작은 인덱스를 반환함
def binary_search(array, target):
start, end = 0, len(array) - 1
while start <= end:
mid = (start + end) // 2
if array[mid] == target:
while mid > 0:
if array[mid - 1] == target:
mid -= 1
else:
break
return mid
elif array[mid] > target:
end = mid - 1
else:
start = mid + 1
return None
n = int(sys.stdin.readline())
cards = list(map(int, sys.stdin.readline().split()))
m = int(sys.stdin.readline())
my_cards = list(map(int, sys.stdin.readline().split()))
cards.sort()
for card in my_cards:
idx = binary_search(cards, card)
if idx is not None:
count = 0
for i in range(idx, len(cards)):
if cards[i] == card:
count += 1
else:
break
print(count, end = ' ')
else:
print(0, end = ' ')빠른 입력을 위해 sys.stdin.readlin()도 사용하고 이분 탐색을 통해 탐색 범위를 대폭 줄였음에도 불구하고 59% 정도에서 시간 초과가 발생했다. 더 시간을 줄이기 위해 딕셔너리를 사용하였다.
import sys
# 찾는 값의 가장 작은 인덱스를 반환함
def binary_search(array, target):
start, end = 0, len(array) - 1
while start <= end:
mid = (start + end) // 2
if array[mid] == target:
while mid > 0:
if array[mid - 1] == target:
mid -= 1
else:
break
return mid
elif array[mid] > target:
end = mid - 1
else:
start = mid + 1
return None
n = int(sys.stdin.readline())
cards = list(map(int, sys.stdin.readline().split()))
m = int(sys.stdin.readline())
my_cards = list(map(int, sys.stdin.readline().split()))
cards.sort()
card_dict = {}
for card in my_cards:
if card not in card_dict:
idx = binary_search(cards, card)
if idx is not None:
count = 0
for i in range(idx, len(cards)):
if cards[i] == card:
count += 1
else:
break
else:
count = 0
card_dict[card] = count
print(' '.join(str(card_dict[x]) for x in my_cards))찾는 카드의 숫자를 key 값, 찾는 카드의 개수를 value 값으로 딕셔너리를 만들어 중복되는 값을 찾는 시간을 대폭 줄였다. 예를 들어 숫자 카드 6의 개수를 10번 연속 카드들에서 찾는 경우 최초 한번만 탐색을 통해 개수를 세고 그 다음부터는 딕셔너리에 저장된 값을 사용하는 원리이다.
6. 문제 링크
