목차
문제
숫자 카드는 정수 하나가 적혀져 있는 카드이다. 상근이는 숫자 카드 N개를 가지고 있다. 정수 M개가 주어졌을 때, 이 수가 적혀있는 숫자 카드를 상근이가 몇 개 가지고 있는지 구하는 프로그램을 작성하시오.
입력
첫째 줄에 상근이가 가지고 있는 숫자 카드의 개수 N(1 ≤ N ≤ 500,000)이 주어진다. 둘째 줄에는 숫자 카드에 적혀있는 정수가 주어진다. 숫자 카드에 적혀있는 수는 -10,000,000보다 크거나 같고, 10,000,000보다 작거나 같다.
셋째 줄에는 M(1 ≤ M ≤ 500,000)이 주어진다. 넷째 줄에는 상근이가 몇 개 가지고 있는 숫자 카드인지 구해야 할 M개의 정수가 주어지며, 이 수는 공백으로 구분되어져 있다. 이 수도 -10,000,000보다 크거나 같고, 10,000,000보다 작거나 같다.
출력
첫째 줄에 입력으로 주어진 M개의 수에 대해서, 각 수가 적힌 숫자 카드를 상근이가 몇 개 가지고 있는지를 공백으로 구분해 출력한다.
예제
입력
10
6 3 2 10 10 10 -10 -10 7 3
8
10 9 -5 2 3 4 5 -10
Plain Text
복사
출력
3 0 0 1 2 0 0 2
Plain Text
복사
풀이
import sys
# input
N = int(sys.stdin.readline()) # 가지고 있는 카드 개수
cards = list(map(int, sys.stdin.readline().split())) # 숫자 카드 리스트
cards.sort()
M = int(sys.stdin.readline()) # 찾아야 되는 정수의 개수
find_list = list(map(int, sys.stdin.readline().split())) # 찾아야 되는 리스트
# Search Program
def low_search(cards, value, start): # 동일한 값이 있는 경우 아래 부분 search
count = 0
left = start - 1
while cards[left] == value:
count += 1
left -= 1
if left < 0: break
return count
def upper_search(cards, value, start): # 동일한 값이 있는 경우 윗 부분 search
count = 0
right = start + 1
while cards[right] == value:
count += 1
right += 1
if right > len(cards)-1: break
return count
def bin_search(cards, value):
pl = 0
pr = len(cards)-1
count = 0
while (pl <= pr):
mid = (pl + pr) // 2
if cards[mid] < value:
pl = mid + 1
elif cards[mid] > value:
pr = mid - 1
else: # 알맞은 값을 찾았다면, 위 아래로 동일한 값이 있는지 확인해야 함
count += 1
if (mid==0 | mid==(len(cards)-1)):
return count
else:
count += low_search(cards, value, mid) + upper_search(cards, value, mid)
return count
return count
count_dic = {} #시간 단축을 위한 dictionary 생성
for value in find_list:
if value not in count_dic:
count_dic[value] = bin_search(cards, value)
print(' '.join(str(count_dic[value]) for value in find_list))
Python
복사
기억할 점
•
count 관련 문제에서 만약 이미 계산해놓은 값인데 또 계산하면 시간이 오래 걸린다. 따라서 dictionary 등으로 저장해두어서 불러오게끔 하면 시간을 단축시킬 수 있다.