백준 17298 [오큰수] 파이썬

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

 

스택이라고 생각을 해서 그런지 쉽게 풀었다. 이제 어떤 경우에 스택을 사용해야 할지 조금씩 감이 잡히는 듯 하다.

#백준 17298 오큰수
import sys
N=int(sys.stdin.readline()) # N 입력처리
lst=list(map(int,sys.stdin.readline().split())) # 받을 데이터 처리
stack=[] # 스택 생성
ans=[] # 정답 저장할 리스트 생성
for i in range(N-1,-1,-1): #뒤에서부터
    element=lst.pop() #element 추출
    if not stack: # 스택이 비어있다면
        ans.append(-1) # -1 ans 추가
        stack.append(element) # element 추가

    elif stack[-1]>element: #스택의 마지막 값 보다 현재 값이 작다면
        ans.append(stack[-1]) # 스택의 마지막 값 ans 추가
        stack.append(element) # element 추가

    else: #스택의 마지막 값 이 현재 값과 같거나 작다면
        if stack: #스택이 존재하면
            while stack: # 스택이 있는동안 스택의 마지막 값이 현재 값보다 큰 경우가 나올때까지 스택을 pop
                if stack[-1]<=element: 
                    stack.pop()
                else:
                    ans.append(stack[-1])
                    stack.append(element)
                    break
            if not stack:
                ans.append(-1)
                stack.append(element)
        else: #그렇지 않다면 (사실상 없어도 되는 코드)
            ans.append(-1)
            stack.append(element)

ans.reverse() #뒤에서 부터 처리했으므로 정답 리스트 reverse

print(*ans)

뒤에서부터 처리해주면서, 현재 값이 스택에 있는 값보다 작은지 확인한다.

작다면 --> 스택 추가

크다면 --> 더 큰값이 존재할때까지 스택pop

스택이 비어있다면 --> 스택 추가