[백준(BOJ)] #17298- 오큰수 (파이썬, PyPy3)

문제

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

17298번: 오큰수

 

---

문제 풀이

저는 스택 자료구조를 사용해서 이 문제를 풀었습니다.

 

2022.06.29 - [CS/자료구조] - [파이썬으로 배우는 자료구조] 스택(Stack), 큐(Queue)

[파이썬으로 배우는 자료구조] 스택(Stack), 큐(Queue)

 

1) A[i]보다 오른쪽에 있으면서 큰 수 중 가장 왼쪽에 있는 수를 구하기 위해 배열을 거꾸로 순회.

2) 스택, 결과를 담을 배열을 사용.

3) 배열을 거꾸로 순회하면서 스택에서 가장 위에 있는 값이 기준 값보다 커질 때까지 pop. 이 과정에서 스택이 비게 되면 기준 값보다 큰 값이 없다는 것을 의미하므로 오큰수는 존재하지 않고, 그렇지 않으면 스택에서 가장 위에 있는 값이 오큰수가 됨.

4) 배열 원소마다 3) 과정이 끝나면 스택에 값을 저장.

 

 

예제 입력 1을 가지고 풀어보도록 하겠습니다. 입력으로 주어진 배열 A와 스택, 그리고 오큰수의 배열을 담을 배열 res를 준비합니다.

 

배열 A를 거꾸로 돌아줍니다. 기준 값은 7이 됩니다. 스택이 비어있으므로 7의 오큰수는 없습니다. 따라서 없다는 값인 -1을 res의 7의 자리에 저장하고 스택에 7을 넣어줍니다.

 

기준 값은 2가 됩니다. 스택에서 가장 위에 있는 값 7은 2보다 크므로 2의 오큰수가 됩니다. res의 2의 자리에 7을 저장하고 2를 스택에 넣어줍니다.

 

기준 값은 5가 됩니다. 스택에서 가장 위에 있는 값은 2이고 2는 5보다 크지 않습니다. 따라서 2를 스택에서 제거합니다. 스택에서 다음에 있는 수는 7로 5보다 큽니다. 따라서 7이 5의 오큰수가 됩니다. res의 5의 자리에 7을 저장하고 5를 스택에 넣어줍니다.

 

기준 값은 3이 됩니다. 스택에서 가장 위에 있는 값 5는 3보다 크므로 3의 오큰수가 됩니다. res의 3의 자리에 5를 저장하고 3을 스택에 넣어줍니다.

 

배열을 모두 순회하여 

 

5 7 7 -1 이라는 오큰수 배열을 얻었습니다.

 

---

구현

코드

import sys
input = sys.stdin.readline

if __name__ == "__main__":
    N = int(input())
    A = list(map(int, input().split()))
    stack = list()
    res = [-1] * N

    for i in range(N - 1, -1, -1):
        # 스택이 비어있지 않으면서 스택 가장 위에 있는 값이
        # 기준 값보다 크지 않으면 스택에서 제거
        while stack and stack[-1] <= A[i]:
            stack.pop()
        # 위 과정이 끝나고 스택이 비어있지 않으면 오큰수가 존재한다는 뜻
        if stack:
            res[i] = stack[-1]
        stack.append(A[i])

    print(*res)

 

결과