BOJ 17299 오등큰수 (python)

https://www.acmicpc.net/problem/17299
스택문제

코드 1

import sys
input = sys.stdin.readline

n = int(input())
cntdict = dict()
ilist = list(map(int, input().split()))
if n == 1:
    print(-1)
else:
    stk = []
    for idx , num in enumerate(ilist):
        if num in cntdict:
            cntdict[num] +=1
        else:
            cntdict[num] = 1

        while len(stk) > 0 and cntdict[ilist[stk[-1]]] < cntdict[num]:
            ilist[stk[-1]] = num
            stk.pop()
        
        stk.append(idx)

    for x in stk:
        ilist[x] = -1
    print(' '.join(map(str,ilist )))

입력된 숫자와 숫자의 개수를 cntdict에 저장하고 stk에 인덱스를 저장하여
a(i)와 a(i+1)의 개수를 비교하여 오른쪽이 더 클 경우 stk에서 pop을 진행하여 왼쪽 숫자를 변경
개수 비교를 마친 후 stk에 남아있는 인덱스는 모두 -1로 초기화 시켜준다

예제 케이스는 통과했으나 오답으로 나와 다른 값을 넣어봄

케이스2
입력 : 7
1 1 2 2 2 3 3
결과: -1 -1 -1 -1 -1 -1 -1

중복에 대한 처리를 별도로 하지 않아
a(i)에 대해 a(i+1)가 첫 등장(개수가 1부터 시작) 할 경우 stk의 top이 변경되어
제대로 된 값을 도출해 낼 수가 없음, 케이스 2 같은 경우 2의 개수가 1보다 많지만
2의 개수가 3으로 되는 시점의 stk의 top는 2 고 남은 숫자 3의 개수가 2개이므로 1에 대한 연산이
제대로 이루어지지 않고 3의 개수는 2이므로 모두 -1로 초기화 시켜버림

대안1

1. cntdict에 누적하는 반복문을 미리 계산 후 진행

코드2

import sys
input = sys.stdin.readline

#n,k = map(int,input().split())
#n,m,b = map(int,input().split())
n = int(input())
#ilist = [list(map(int,input().split())) for _ in range(n)]
#ilist = [int(input()) for _ in range(n)]

cntdict = dict()

ilist = list(map(int, input().split()))
stk2 = []
if n == 1:
    print(-1)
else:
    stk = []

    for idx , num in enumerate(ilist):
        if num in cntdict:
            cntdict[num] +=1
        else:
            cntdict[num] = 1

    for idx , num in enumerate(ilist):
        
        while len(stk) > 0 and cntdict[ilist[stk[-1]]] < cntdict[num]:
            ilist[stk[-1]] = num
            stk.pop()
        stk.append(idx)
        
    for x in stk:
        ilist[x] = -1
    print(' '.join(map(str,ilist )))

첫 제출에 오답이 나오고 왜 틀렸는지 생각이 나지 않아
반례를 검색했으나 반례를 찾을 수 없어 직접 떠올리는 과정이 생각보다 오래 걸림
문제를 대충 읽고 여제 입력을 보고 문제를 이해하려고 하니 이런 결과가 나오는 거 같음