[백준] 17298 - 오등큰수 - (python 파이썬)

문제링크 : https://www.acmicpc.net/problem/17299

17299번: 오등큰수

 

 

풀이과정 : 바로 전에 풀었던 오큰수와 흡사한 문제지만, 배울것이 있는 문제였다.

등장횟수를 기준으로 삽입하는것이기 때문에, 처음에는 count_lst 라는 리스트를 만들어

그 안에 lst.count[lst[i]] 이런식으로 만들어 for문을 돌려 길이가 N인 등장횟수 리스트를 

만든 뒤에, 전 문제랑 같은 형식으로 풀었다. 그랬더니 역시 시간초과,,,!

길이가 N인 리스트를 count과정을 N번 하다보니 O(n**2)가 되어 count_lst를 만드는

과정에서 시간초과가 났을것이라 생각한다. 그래서 필요한 것이 Counter함수다.

Counter함수는 collection 모듈에 포함되어 있는 함수로, 컨테이너 등에 동일한 자료가

몇 개인지 확인하고 딕셔너리 형태로 출력해주는 객체다. 

 

 

 

 

 

가령 이 문제에서 처럼 입력을 주어주면 빈도수가 많은것 부터 그의 횟수를 차례대로

딕셔너리 형태로 출력해준다.

이 Counter함수를 통해서 O(n)의 시간으로 count_lst를 만드는것이 핵심이고,

나머지는 오큰수와 형태가 거의 같다.

 

 

import sys
from collections import Counter

N = int(input())
lst = list(map(int, sys.stdin.readline().split()))
count_lst = Counter(lst) #등장횟수를 정리해놓은 dic

answer = [-1] * N #디폴트를 -1로 걸어놓은 리스트
stack = [] #현재 가르키는 인덱스를 저장해놓을 스택
stack.append(0)
for i in range(1, N):
    while stack and count_lst[lst[stack[-1]]] < count_lst[lst[i]]:
        answer[stack.pop()] = lst[i]
    stack.append(i)
print(*answer)

답(이미지)

 

 

후기 : 골드도 이제 풀 수 있는 반열에 올랐다...! 역시 많이 보면 는다...!