[백준/Python] 10816번 숫자 카드 2 문제

■ 10816번 숫자 카드 2 문제

 

출처: 백준 10816번 숫자 카드 2 문제

 

 

■ 첫 번째 코드: 시간초과

 

먼저 제가 처음 작성했던 코드입니다. 저는 파이썬 딕셔너리를 활용하여 문제를 풀려고 했습니다. 먼저 모든 값을 list로 받고, count 메서드를 활용하여 '숫자: 개수' 쌍의 딕셔너리를 만들었습니다. 그리고 확인해야 하는 숫자를 key로 해서 값이 있으면 개수를 출력하고 없으면 0을 출력하도록 코드를 작성했습니다. 

결론적으로 아래의 코드는 시간 초과가 발생했습니다. 코드를 쭉 살펴보니 시간이 크게 소요되는 구간은 list의 값을 하나하나 count 하여 dict를 만드는 구간 정도인 것 같았습니다. 그래서 이 구간을 이미 사전에 정의된 라이브러리를 활용해 두 번째 코드로 바꿔 봤습니다.

 

M = int(input())
card_list = list(map(int, input().split()))
card_dict = {}

for card in set(card_list): # key가 card이고 value가 개수인 dict
    card_dict[card] = card_list.count(card)

N = int(input())
target_list = list(map(int, input().split()))

for target in target_list:
    try:
        print(card_dict[target], end = ' ')
    except KeyError:
        print(0, end = ' ')

 

■ 두 번째 코드: 816 ms (통과)

 

위의 첫 번째 코드에서 딕셔너리를 만드는 부분을 Counter 함수를 활용하여 바꿔 봤습니다. 파이썬은 같은 기능을 한다면, 기본적으로 제가 임의로 작성한 코드 보다 자체 라이브러리를 활용하는 것이 더 빠르다는 것을 새삼 느꼈습니다.

참고로 Counter 함수는 list 같은 자료형을 넣으면 각 element 별로 몇 개인지 개수를 '값 : 개수' 형태의 딕셔너리로 반환해 줍니다. (정확히는 Counter 객체이지만, 딕셔너리처럼 활용 가능)

from collections import Counter

M = int(input())
card_list = list(map(int, input().split()))

card_dict = Counter(card_list) # list의 값이 몇개 있는지 Count해서 dict로 반환

N = int(input())
target_list = list(map(int, input().split()))

for target in target_list:
    if target in card_dict:
        print(card_dict[target], end = ' ')
    else:
        print(0, end = ' ')

 

■ 세 번째 코드: 656 ms (속도 향상)

 

스터디용으로 다른 분이 작성하신 코드를 참고하여 두 번째 코드를 아래와 같이 바꿔 봤습니다. 바꾼 코드는 맨 밑의 출력 부분입니다. 두 번째 코드에서는 단순하게 target_list를 순회하면서 값을 출력했다면, 세 번째 코드는 list comprehension과 삼항 연산을 이용하여 출력 부분만 바꿨습니다.

일반적인 list보다 list comprehension과 삼항 연산 등을 활용하는 것이 더 빠를 수 있다고는 알고 있었지만, 속도 향상의 정도가 생각보다 커서 조금 놀랐네요. 역시 오늘도 좋은 공부가 된 것 같습니다. list comprehension과 삼항 연산에 대해서는 제가 참고한 글의 링크를 아래 넣어두었으니 참고해 주세요.

 

from collections import Counter

M = int(input())
card_list = list(map(int, input().split()))

card_dict = Counter(card_list) # list의 값이 몇개 있는지 Count해서 dict로 반환

N = int(input())
target_list = list(map(int, input().split()))

print(' '.join([str(card_dict[target]) if target in card_dict else str(0) for target in target_list]))

 

 

[python]리스트 컴프리핸션에서 if문 사용하기 | Daily Programming (jinmay.github.io)

[python]리스트 컴프리핸션에서 if문 사용하기