[BOJ] 17299번 - 오등큰수

---

문제설명

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

17299번: 오등큰수

사고과정

• 저번 오큰수 문제로 스택을 활용해서 풀려고 했는데 어려웠다.. 단어의 개수가 추가된 것이 조금 응용된 것인데 이거를 잘 해결해내지 못했다..
• 구글링을 해보니 핵심 풀이는 각 수열 원소에다가 수열에 존재하는 단어 개수를 추가하면 된다. 예를 들어, 수열이 [1, 1, 2, 3, 4, 2, 1] 이 주어졌다면 (원소 개수, 원소) 로 해서 [(3, 1), (3, 1), (2, 2), (1, 3), (1, 4), (2, 2), (3, 1)] 이런식으로 만들어 준다. 그리고 스택에다가 저번 처럼 인덱스를 집어넣고 while 문을 활용한다. 인덱스 0을 초기에 넣어주고 하나씩 증가할 때마다 다음 인덱스 원소의 개수 > 스택의 마지막에 있는 인덱스가 가리키는 원소의 개수가 되면 answer에 오등큰수를 입력하고 스택에 있는 값을 빼준다.
• 아직 응용이 어렵다..

풀이(스스로 못 푼 풀이)

import sys
from collections import Counter

input = sys.stdin.readline
n = int(input().rstrip())
A = list(map(int, input().split()))

cnt = Counter(A)
A = [(cnt[num], int(num)) for num in A]  # 개수, 원소
answer = [-1] * n
stack = []
stack.append(0)

for i in range(1, n):
    while stack and A[stack[-1]][0] < A[i][0]:
        answer[stack.pop()] = A[i][1]
    stack.append(i)

for a in answer:
    print(a, end=' ')