[백준 / python] #11652 카드

첫 번째 시도

input = __import__('sys').stdin.readline

d = dict()
for _ in range(int(input())):
    n = input()
    if n in d.keys(): d[n] += 1
    else: d[n] = 1

max_value = max(list(d.values()))
pos_keys = list()
neg_keys = list()
for i in d.keys():
    if int(i) > 0:
        pos_keys.append(i)
        pos_keys.sort()
    if int(i) <= 0:
        neg_keys.append(i)
        neg_keys.sort()
        neg_keys.reverse()
dic_keys = neg_keys + pos_keys
# print(dic_keys)

for key in dic_keys:
    if d[key] == max_value:
        print(key)
        break

사실 진짜 첫 번째 시도한 코드는 아니지만, 전체 코드를 두 번 갈아엎어서 초반의 코드를 대표하여 기록하였다.

시간 초과가 자꾸 발생하여 빠른 입력을 넣어주었고, 각 카드를 key, 그 개수를 value로 하여 딕셔너리 자료형 변수에 담았다.

그리고 음수와 양수가 정렬 과정에서 반대로 움직이길래 분리해서 정리했다.

하지만 이 또한 결과는 시간 초과였다. 아무래도 전체 흐름 자체가 너무 길게 짜인 것 같아서 어떻게 하면 코드를 줄일 수 있을지 고민하였다.

두 번째 시도

import sys
input = sys.stdin.readline

t = int(input())
li = list()
cnt = list()
for _ in range(t):
    li.append(int(input()))
    li.sort()
for elem in li:
    # print(elem, li.count(elem))
    cnt.append(li.count(elem))
print(li[cnt.index(max(cnt))])

코드를 싹 날리고 다시 짜 봤다. 이 번에는 정렬이 음수를 포함해도 문제를 일으키지 않아서 그냥 했다. 확실히 코드가 짧아졌음을 느꼈지만, 그럼에도 불구하고 결과는 시간 초과였다.

두 경우 모두에서 시간 초과가 발생하니 우선적으로 고려하고 싶었던 부분은 반복문의 감소였다. 우선 리스트 타입 변수가 여러 개 존재하여 로직상 반복문이 여러 개 등장한다고 가정하였다. 그렇다면 이 문제에서 처음 떠올렸던 것처럼 효율적으로 숫자들을 관리할 수 있는 딕셔너리 타입의 변수를 하나 이용하고, 이를 정렬하는 방법만 제대로 적용하면 시간을 단축시킬 수 있을 것이라 생각하였다.

세 번째 시도

import sys
input = sys.stdin.readline

t = int(input())
d = dict()
for _ in range(t):
    n = int(input())
    if n in d.keys(): d[n] += 1
    else: d[n] = 1
new_d = list(d.items())
new_d.sort(key=lambda x : (-x[1], x[0]))
print(new_d[0][0])

딕셔너리 타입에 key, value로 카드와 그 갯수를 매핑하고, sort 메소드와 sorted 메소드의 사용법을 좀 더 알아봐서 정렬하는 방법을 학습하였다.

sort메소드의 정렬 기준을 설정할 수 있는 파라미터 key는 람다 함수를 이용하여 좀 더 디테일하게 정렬 기준을 설정할 수 있었다. 이 문제에서는, value 값을 내림차순으로 정렬하여 가장 많이 가지고 있는 카드가 앞에 오게 하고, 동점일 경우에는 key 값을 오름차순으로 정렬하여 작은 수의 카드를 출력하게끔 하였다.

다행히 시간이 많이 단축되는 경험을 할 수 있었다.

---

더더욱 신기한 점은, 처음에는 빠른 입력을 하지 않고 돌려서 정답을 맞췄는데, 엄청 오래 걸렸었다. 갑자기 빠른 입력이 얼마나 큰 효과를 주는지 궁금하여 빠른 입력을 적용하지 않은 버전과 적용한 버전의 시간을 비교하였더니 약 29배 정도의 성능 향상을 보여주었다… 우선 입력되는 숫자의 범위를 체크해보고 시간 초과가 무서운 문제를 만나면 일단 빠른 입력부터 적어두고 시작해야겠다…

빠른 입력 적용 전:

빠른 입력 적용 후: