012 오큰수

첫번째 코드

 

책에서 말한 큐와 스택을 이용하여 문제를 푸는데 어떻게 작성해야할 지 몰라 책을 참고했다!

 

처음에 계속 의문이었지만 코드를 작성하고 디버깅으로 돌리면서 이해했다!

stack 리스트에는 인덱스가 들어간다고 생각하면 편하다

 

만약 다음 값이 크면,

    stack에 값이 있고 A[stack]가 A[i]보다 작을때 계속 해서 반복

    answer[stack]에 A[i] 부여 (A[i]값이 더 큰거니까)

    stack에 i 인덱스 추가

 위의 과정을 반복하고

 

만약 이후에 stack에 원소가 존재하면

그것은 왼쪽에 현재보다 더 큰수가 없었다는 의미이므로 -1를 출력해야한다.

 

그렇게 결과를 만들어내면 된다!

 

import sys
input = sys.stdin.readline

n = int(input())
A = list(map(int, input().split()))

stack = []
answer = [0] * n

for i in range(n):
    while stack and A[stack[-1]] < A[i]:
        answer[stack.pop()] = A[i]
    stack.append(i)

while stack:
    answer[stack.pop()] = -1

print(*answer)

 

통과!

 

근데 이해도 어려웠고, 코딩 작성 후에도 이해가 어려워서

다음에 물론 풀어볼 문제지만 그때도 여전히 풀 수 있는지 의문이댜...

계속 풀다보면 큐와 스택 마스터리가 될 수 있겠지!

---

링크

https://github.com/ornni/programmers/tree/main/%EB%B0%B1%EC%A4%80/Gold/17298.%E2%80%85%EC%98%A4%ED%81%B0%EC%88%98

programmers/백준/Gold/17298. 오큰수 at main · ornni/programmers