골드 5 오큰수

문제: 골드 5 오큰수

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

 

풀이코드

import sys
input = sys.stdin.readline

N = int(input())
lst = list(map(int, input().split()))
s = []  ## 오큰수를 아직 찾지 못한 수들의 인덱스를 넣어두는 스택
ans =[-1] * N

for i in range(N): 
    while len(s) > 0 and lst[s[-1]] < lst[i]: 
        j = s[-1]
        ans[j] = lst[i]
        s.pop()
    s.append(i)
print(*ans)

---

느낀 점

너무 헷갈렸다. ...ㅠㅠ

일단 스택에 뭘 넣고 뺄지를 생각해야 한다. 이중 for문으로 하면 무조건 시간초과가 난다. 

for문으로 lst를 돌되 만약 계속해서 오큰수를 찾지 못한다면 스택에 남아있어야 한다. 그리고 오큰수를 찾으면 그 숫자의 오큰수가 이거다! 하고 정답을 반환해야 한다.

 

그렇다면 일단 스택은 오큰수를 아직 찾지 못한 수들의 인덱스를 넣어두는 곳이어야 한다. 왜 하필 인덱스여야 할까? 만약 못 찾고 스택에 계속 남아있다면 그 숫자의 오큰수는 -1이어야 한다. 그렇다면 ans라는 리스트를 -1로 미리 채워두고 해당 수의 인덱스를 오큰수를 찾으면 그 값으로 치환해주면 편하기 때문에 인덱스를 넣어두는 것이다. 

 

생각해보자. while문을 갖다가 만약 스택이 비어있지 않고 현재 지금 스택 안에 오큰수를 찾지 못한 가장 top의 수가 새로 들어온 수보다 작다면 오큰수를 찾은 것이다. 

그렇게 되면 해당 인덱스를 저장하고 ans라는 리스트의 해당 위치에 찾은 오큰수를 넣어준다. 그러고 스택 안에 있던 건 오큰수를 찾았기 때문에 pop해준다. 

 

만약 첫 번째 수이거나 스택에 있는 수보다 작은 수가 들어온다면 바로 스택에 넣어줘야 하기 때문에 while 문 바깥에는 append를 시켜준다. 

 

직접 써보는 게 도움이 많이 된다. 그리고 무작정 스택을 만들고 생각하는 것보다 그걸 갖다가 어디에 쓸지, 뭘 집어넣을지를 먼저 생각하는 게 맞는 것 같다.