[python] 11652번: 카드 시간초과 해결

11652: 카드

5달 전 내 코드

시간초과가 어디서 나는 건지 질문을 올렸다. list.count(값)을 하면 리스트를 다 돌면서 개수를 세는 것이기 때문에 O(N)이 된다. 이게 for문 안에 있으니 최대 O(N x 263)이 되어서 "시간초과가 안 나오면 이상한 상황"이었다.

import sys
from typing import OrderedDict

n = int(sys.stdin.readline().rstrip())
cardList = [int(sys.stdin.readline().rstrip()) for col in range(n)]
setCard = list(set(cardList)) # 숫자 카드의 종류
cardAndNum = dict() # { '숫자 카드' : '몇개'}

for i in range(len(setCard)):
    cardAndNum[setCard[i]] = cardList.count(setCard[i])

cardAndNum = dict(OrderedDict(
    sorted(cardAndNum.items(), key=lambda item: (-item[1], item[0]))))

print(list(cardAndNum.keys())[0])

접근법

list를 입력받은 후에 cnt, maxNum, maxCnt에 값을 저장해서 갱신하는 방식이다.

• cnt: 현위치에 있는 숫자가 나오는 횟수
• maxNum: 가장 자주 나온 숫자
• maxCnt: 가장 자주 나온 숫자의 횟수

코드 순서

1. numList = sorted(numList): 숫자가 몇 개 있는지 셀 때는 정렬되어 있어야 한다.
2. cnt, maxNum, macCnt = 1, 첫번째 카드 숫자, 1로 초기화하는 이유: 입력받을 리스트의 크기는 N (1 ≤ N ≤ 100,000)이다. 따라서 무조건 1개의 카드는 있기 때문에 맨 앞에 있는 카드로 초기화한다.
3. if index > numLen-1: 입력받은 리스트가 [1,1,2,2,2]일 때 마지막 2를 지나면 이 if문에 도달한다. 이 코드가 있어야 maxNum = 2, maxCnt = 3로 값을 최댓값을 갱신할 수 있다.

코드

import sys
input = sys.stdin.readline


def getMostCountNum() -> int:
    cnt, maxNum, maxCnt = 1, numList[0], 1
    for index in range(1, numLen+1):
        if index > numLen-1 or numList[index-1] != numList[index]:
            if cnt > maxCnt:
                maxCnt = cnt
                maxNum = numList[index-1]
            cnt = 1
        else:
            cnt += 1

    return maxNum


numLen = int(input().rstrip())
numList = [0]*numLen

for i in range(numLen):
    numList[i] = int(input().rstrip())
numList = sorted(numList)

print(getMostCountNum())

참고 링크

짖는 개 선생님은 나의 스승님