백준 11652번 카드

NameError·2021년 5월 9일

문제 링크

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

풀이 전 계획과 생각

앞에서 풀었던 5430번 AC는 입력 형식 자체가 너무 복잡했는데 이번에는 단순히 엔터 키로 정수를 구분하는 입력 형식으로 되어 있어서 일단 간단하게 접근할 수 있었다.

이 문제의 핵심은 가장 많이 나오는 정수(그게 몇 번째인지는 전혀 알 필요가 없다.)를 출력하는 것이다. 그리고 최대 출력 횟수에 해당하는 정수가 여러 개라면 그 중에서 가장 작은 정수를 출력하도록 되어 있다.

딕셔너리를 이용하여 입력되는 정수를 카운팅하고 그 딕셔너리에서 가장 큰 값이 할당된 키를 찾아서 출력하는 간단한 구조로 일단 구현해 보았는데... 한 번에 합격했고 시간도 파이썬으로 합격한 제출자들 중 상위권이라서 뿌듯하다! ㅋㅋㅋ

풀이 (코드 블록 첨부)

import sys

N = int(sys.stdin.readline())
#cards_arr = [0 for x in range(N)]
count_dict={}
for x in range(N):
    c = int(sys.stdin.readline())
    if c not in count_dict:
        count_dict[c]=1
    else:
        count_dict[c]=count_dict[c]+1
#print(max(count_dict))
max_card=-4611686018427387905
max_count=0
for element in count_dict:
    if count_dict[element]>max_count:
        max_card=element
        max_count=count_dict[element]
    elif count_dict[element]==max_count and element<max_card:
        max_card=element
print(max_card)

풀이하면서 막혔던 점과 고민

쉽게 생각해서 즉시 제출하려다가... 해당 문제의 질문 게시판에서 마지막으로 반례를 확인해보려고 들어가보니 예상 외의 함정이 있었다!

입력되는 카드의 키값이 모두 0보다 큰 자연수일 줄 알았는데 최솟값이 -(2^62)라는 것이었다.
그러니까 가장 많이 나오는 카드의 번호의 최솟값을 찾는 알고리즘에서 초기화를 0으로 하면 안 되고 -(2^62)-1로 해야 한다.
그리고 큰 수 계산기 사이트에 따르면 -(2^62)는 -4611686018427387904이다.
그래서 비교할 카드번호 초깃값을 0이 아닌 -4611686018427387905로 정했다.

이 수가 너무 큰 것 같아서 초깃값을 정하는 알고리즘을 여러가지로 바꾸어 보았는데(현재 입력받은 값들 중 최솟값으로 정하거나) 오히려 시간이 길어지거나 그대로였다. 아마도 채점 프로그램에 입력된 테스트 케이스가 -4611686018427387904 근처인가보다.