210531 완전/이진탐색 - 숫자카드2

문제주소 : https://www.acmicpc.net/problem/10816

 

이중 for문으로 결과를 내기는 쉬웠으나 시간초과 해결이 어려웠다. 

dict를 이용해 이중 for문을 2개의 for문으로 바꿔서 해결할 수 있었다.

 

이중 for문

import sys

# 입력값 넘겨받기
n = int(sys.stdin.readline())
value_n = list(map(int, sys.stdin.readline().split()))
m = int(sys.stdin.readline())
value_m = list(map(int, sys.stdin.readline().split()))

# 개수세기 - 완전탐색 -> 시간초과로 실패
count = [0] * m
value_n.sort()

for i in range(m):
    for j in range(n):
        if value_m[i] == value_n[j]:
            count[i] += 1
        if value_m[i] < value_n[j]:
            break

# 출력
for x in count:
    sys.stdout.write(str(x) + " ")

최대한 시간을 줄이기 위해 sort도 해보고 입력 출력구문도 바꿔보았지만 최종적으로 실패했다.

 

 

dict를 이용한 2개의 for문

import sys

# 입력값 넘겨받기
n = int(sys.stdin.readline())
value_n = list(map(int, sys.stdin.readline().split()))
m = int(sys.stdin.readline())
value_m = list(map(int, sys.stdin.readline().split()))

# 개수세기 - 딕셔너리에 해당 숫자를 가진 개수를 누적 COUNT해서 조회만 함
count = {}

for i in range(n):
    try:
        count[value_n[i]] += 1
    except:
        count[value_n[i]] = 1

for j in range(m):
    try:
        sys.stdout.write(str(count[value_m[j]]) + " ")
    except:
        sys.stdout.write(str(0) + " ")

 

count[value_n[i]]를 if문으로 확인하는 방법이 잘 안됐지만 결과적으로 이게 더 편한것 같다.