[백준] 17298번 : 오큰수(스택)- 파이썬[Python]

문제

17298번: 오큰수

풀이

import sys

stack=[]
t=int(sys.stdin.readline())
list1=list(map(int,sys.stdin.readline().split()))

for i in range(len(list1)-1):
  stack.append(i)
  
  while stack!=[] and list1[stack[-1]]<list1[i+1]:
      list1[stack[-1]]=list1[i+1]
      stack.pop()
if stack:
  for p in stack:
    list1[p]=-1
list1[-1]=-1
for i in range(t): 
  print(list1[i], end = " ")

수 많은 시행착오 끝에 푼 문제이다.

처음에는 스택으로 어떻게 풀어야 할지 감이 오질 않아서 for문으로 코드를 작성했는데 아니나 다를까 시간 초과 처리가 되었다.

스택 개념을 다시 숙지하고 최대한 반복을 줄이기 위해서 바로 우측의 숫자로 오큰수 판별이 되지않는 숫자의 인덱스만 스택으로 쌓고, 따로 for문을 돌려서 오큰수로 만드는 코드를 짰지만, 채점 50%정도에서 시간초과가 발생했다..

많은 고민 끝에 큰수에서 작은 수로 스택이 쌓이는 규칙을 발견하여 while 조건문으로 필요한 상황에만 while문이 돌아가게 코드를 짠 후에 정답처리를 받을 수 있었다.

이 문제를 풀면서 최대한 반복을 줄여서 낭비없는 코드를 짜기위해 끝없이 고민해야함을 깨달았다.

 

 

시행착오의 흔적들