[백준 17298] 스택 개념과 풀이 - 파이썬 (Python)

오큰수

문제

크기가 N인 수열 A = A1, A2, ..., AN이 있다. 수열의 각 원소 Ai에 대해서 오큰수 NGE(i)를 구하려고 한다. Ai의 오큰수는 오른쪽에 있으면서 Ai보다 큰 수 중에서 가장 왼쪽에 있는 수를 의미한다. 그러한 수가 없는 경우에 오큰수는 -1이다.

예를 들어, A = [3, 5, 2, 7]인 경우 NGE(1) = 5, NGE(2) = 7, NGE(3) = 7, NGE(4) = -1이다. A = [9, 5, 4, 8]인 경우에는 NGE(1) = -1, NGE(2) = 8, NGE(3) = 8, NGE(4) = -1이다.

---

입력

첫째 줄에 수열 A의 크기 N (1 ≤ N ≤ 1,000,000)이 주어진다. 둘째 줄에 수열 A의 원소 A1, A2, ..., AN (1 ≤ Ai ≤ 1,000,000)이 주어진다.

출력

총 N개의 수 NGE(1), NGE(2), ..., NGE(N)을 공백으로 구분해 출력한다.

---

예제 입력 1

4
3 5 2 7

예제 출력 1

5 7 7 -1

---

파이썬 스택

맨 윗 부분을 TOP이라 합니다

자료 구조 중 하나인 Stack은 상자에 물건을 쌓아 올리듯이 데이터를 쌓는 자료 구조라고 할 수 있습니다.

Stack의 가장 큰 특징은 나중에 들어간 것이 먼저 나오는 (Last In First Out)의 형태를 띈다는 것입니다.

이 방식을 가진 자료구조인 Stack을 활용하여 다양한 문제를 해결할 수 있습니다.

파이썬에서 스택은 일반 리스트를 이용해서 구현할 수 있습니다.

---

스택 초기화

stack = [] # 빈 리스트 생성

 

스택에 값 push

stack.append(1);     # stack에 값 1 추가
stack.append(3);     # stack에 값 3 추가

 

스택 값 pop / 삭제

stack.pop();       # stack에 맨위의 값 리턴하고 제거

 

스택 기타 반환 함수

#아래는 리스트의 함수들인데, 스택이 리스트로 구현했기때문에 이렇게 활용할수 있습니다.

stack[-1]
#poll. 맨위에 값을 확인만하고(반환값) 삭제하지 않습니다
# 스택이 리스트로 구현했기 때문에 리스트 마지막 인덱스 -1이 poll이 됩니다

len(stack)
# 스택 크기 반환

#아래는 리스트의 함수들인데, 스택이 리스트로 구현했기때문에 이렇게 활용할수 있습니다.

stack[-1]
#poll. 맨위에 값을 확인만하고(반환값) 삭제하지 않습니다
# 스택이 리스트로 구현했기 때문에 리스트 마지막 인덱스 -1이 poll이 됩니다

len(stack)
# 스택 크기 반환

---

파이썬 코드

스택을 값 자체말고 인덱스를 저장하는 데 이용할 것입니다.

0 인덱스부터 차례대로 스택에 넣으면서 스택에 top부분에 해당하는 수보다 큰 수가 들어오면 그것이 '오큰수'가 됩니다.

그래서 스택에 있던 기존의 인덱스들을 pop하고, 그 인덱스에 해당하는 오큰수를 그 큰 수로 설정합니다.

push할수록 밑바닥에 있는 수 이하의 수가 들어오므로 오큰수를 놓치지 않을수 있습니다.

스택에 있던 인덱스를 pop하다가 그 큰수 보다 더 큰 것이 오면, 그 스택에 있던 수는 오큰수를 아직 안만난것이므로 마저 push 합니다.

모든 인덱스를 탐색했는데, 스택에 남아있는 수는 오큰수를 만나지 않았으므로 -1이 됩니다.

그러나 초기화를 -1로 해주면 따로 조작할 필요가 없으니, 인덱스 다 탐색하고 스택에 남은 수들은 그대로 두겠습니다.

 

#Stack
import sys
input = sys.stdin.readline
n = int(input())
num = list(map(int , input().split()))
stack = []
A = [-1]*n
stack.append(0)
for i in range(1,n):
    a = num[i]
    while len(stack)!=0:
        top = num[stack[-1]]
        if top < a:
            A[stack.pop()] = a
        else:
            break
    stack.append(i)
result = ""
for ch in A:
    result += str(ch) + ' '
print(result)