백준 10816 - 파이썬

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

10816번: 숫자 카드 2

 

문제 풀이

문제가 어렵지 않아 금방 구현을 해냈고, 아래는 내가 처음 작성한 코드이다.

import sys
input = sys.stdin.readline

n = int(input())
cards = list(map(int,input().split()))

m = int(input())
checks = list(map(int,input().split()))

for check in checks:
    print(cards.count(check), end=" ")

 

하지만 위 코드는 시간 초과가 발생하였다. 리스트를 딕셔너리를 변환시켜 주면 시간 안에 가능할까 싶어 아래의 코드에서는 딕셔너리도 활용해 봤다.

import sys
input = sys.stdin.readline

n = int(input())
cards = list(map(int,input().split()))

m = int(input())
checks = list(map(int,input().split()))

dic = {}
for i in range(m):
    dic[checks[i]] = 0

for key,value in dic.items():
    print(cards.count(key), end=" ")

 

 

하지만 이 역시 시간초과가 발생하여 시간을 더 들인다고 답이 구해질 거 같지 않아 다른 사람의 블로그를 참고했다.

 

import sys
input = sys.stdin.readline

n = int(input())
cards = list(map(int,input().split()))

m = int(input())
checks = list(map(int,input().split()))

count = {}
for card in cards:
    if card in count:
        count[card] += 1
    else:
        count[card] = 1

for check in checks:
    result = count.get(check)
    if result == None:
        print(0, end=" ")
    else:
        print(result, end=" ")

 

이 분의 경우에는 count라는 딕셔너리에 새로운 수가 추가 되는 경우에는 1을 value값에 대입해 주고, 기존에 있는 값이라면 1을 더해줌으로써 각 수가 cards 리스트 안에서 몇 개인지 저장해 놨다. 그러고 나서 딕셔너리의 get함수를 이용하여 답을 출력해 주었다.

 

다음 코드는 이진 탐색을 이용한 것이다.

import sys
input = sys.stdin.readline

n = int(input())
cards = sorted(list(map(int,input().split())))

m = int(input())
checks = list(map(int,input().split()))

count = {}
for card in cards:
    if card in count:
        count[card] += 1
    else:
        count[card] = 1

def binarySearch(arr, target, start, end):
    if start > end:
        return 0
    mid = (start + end) // 2
    if arr[mid] == target:
        return count.get(target)
    elif arr[mid] < target:
        return binarySearch(arr, target, mid+1, end)
    else:
        return binarySearch(arr, target, start, mid-1)
    
for check in checks:
    print(binarySearch(cards, check, 0, len(cards)-1), end=" ")

 

 

이진 탐색도 처음에 풀 때 고려한 방법 중 하나이지만 target지점을 찾았을 때 총 몇개인지를 어떻게 알려줄지를 해결하지 못했었다. 그러한 부분을 위 코드에서는 count 딕셔너리에 각 숫자가 몇 개인지를 저장해 뒀기 때문에 무난히 해결한 모습이다.

 

느낀 점

이번 문제는 한끝 차이로 풀지 못 한 문제인 거 같다. 이진탐색과 딕셔너리를 활용하면 된다는 것은 알고 있었지만 이를 어떻게 사용하는지를 생각해 내지 못한 것이 그 차이인 거 같다. 이런 부분은 갑자기 발상의 전환을 하며 떠올릴 수도 있겠지만 모든 문제에서 그러기는 힘들기 때문에 꾸준히 풀면서 감을 익혀나가는 수밖에 없을 거 같다.