[BOJ] 10816. 숫자 카드2

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

10816번: 숫자 카드 2

 

 

1. 해결방법

"""
1. 아이디어
- N 배열을 정렬
- 이진 탐색으로 검색
-> 시간 초과
- 파이썬의 Counter() 함수를 사용
"""

 

 

2. 정답 코드

# 시간 초과

import sys
input = sys.stdin.readline

N = int(input())
nums = sorted(list(map(int, input().split())))
M = int(input())
targets = list(map(int, input().split()))

answer = []
def search(start, end, tar):
    if start == end:
        return answer.append(0)

    mid = (start + end) // 2
    if nums[mid] == tar:
        return answer.append(nums[start:end + 1].count(tar))
    if nums[mid] < tar:
        search(mid + 1, end, tar)
    else:
        search(start, mid, tar)


for target in targets:
    search(0, N - 1, target)
print(' '.join(map(str, answer)))

# 해결

from collections import Counter
import sys
input = sys.stdin.readline

N = int(input())
nums = sorted(list(map(int, input().split())))
M = int(input())
targets = list(map(int, input().split()))


count = Counter(nums)
for target in targets:
    if target in count:
        print(count[target], end=' ')
    else:
        print(0, end=' ')

이진 탐색에서 자주 사용하는 방식의 코드를 사용하니까 시간 초과가 나왔다.
그래서 파이썬 내장 함수인 Counter() 함수를 사용해서 시간 초과를 해결했는데... Counter() 함수를 공부 좀 해야할 필요가 있다.