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