[BaekJoon] 10816번 : 숫자 카드 2 (Python)

코딩 1일 1문제! 오늘의 문제는 백준의 숫자 카드 2 입니다.

10816번: 숫자 카드 2

첫번째 시도

from collections import Counter

input_num = int(input())
numbers = list(map(int, input().split()))
    
input_num2 = int(input())
numbers2 = list(map(int, input().split()))

answer = []

cnt = Counter(numbers)

exist_num = list(set(numbers))

for num in numbers2:
    if num in exist_num:
        answer.append(str(cnt[num]))
    else:
        answer.append("0")
        
print(" ".join(answer))

먼저 collections의 Counter를 활용하기 위해 import 합니다.

그 다음 입력받을 숫자의 개수와 기준이 될 숫자 목록( numbers )을 입력 받습니다.

그리고 있는지 없는지 확인 할 숫자의 개수와 숫자 목록 ( numbers2 )을 입력 받습니다.

 

numbers를 Counter로 카운팅하고 number의 중복을 제거한 숫자를 exist_num으로 만들어줍니다.

numbers2에서 숫자를 하나씩 꺼내오고 numbers에 존재하는 숫자이면 카운팅한 수를 가져와 answer에 append시켜주고

그렇지 않은 경우에는 0을 append시켜줍니다.

 

마지막으로 answer를 join해서 하나의 문자열로 만들어준 뒤에 프린트해주면 끝!

 

하지만!

Python과 PyPy둘다! 시간 초과!

 

두번째 시도

input_num = int(input())
numbers = list(map(int, input().split()))
sorted_numbers = sorted(numbers)

input_num2 = int(input())
numbers2 = list(map(int, input().split()))
sorted_numbers2 = sorted(numbers2)

cnt_dict = dict()
idx = 0

for num in sorted_numbers2:
    cnt = 0
    
    if num not in cnt_dict.keys():
        while idx < len(numbers):
            if num == sorted_numbers[idx]:
                cnt += 1
                idx += 1
            elif num > sorted_numbers[idx]:
                idx += 1
            else:
                break
        cnt_dict[num] = cnt
        
answer = [str(cnt_dict[num]) for num in numbers2]

print(" ".join(answer))

이번에는 숫자를 정렬한 다음에 카운팅을 직접하기로했습니다.

먼저 입력 받은 숫자 두개를 모두 정렬합니다.

그 다음 정렬한 numbers2에 있는 숫자를 하나씩 꺼내오면서 비교하기로 합니다.

여기서 idx 하나를 두는데 이를 통해 탐색범위를 많이 줄일 수 있습니다.

먼저 꺼내온 숫자가 카운팅한 수를 담아두는 cnt_dict에 없는 경우에만 while 반복문을 돕니다.

sorted_numbers2에서 꺼내온 숫자와 idx위치의 값이 같을 경우나 더 클 경우에 idx를 하나 증가시키고

그렇지 않은 경우는 반복문을 중단합니다.

또는 idx의 값이 numbers의 길이보다 큰 경우에 중단합니다.

 

마지막으로 각 숫자를 카운팅한 수를 answer 리스트에 담아주고 이를 join한 값을 출력하면 끝!

SOMJANG/CODINGTEST_PRACTICE