[BOJ] 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이다.

 

🤖 알고리즘

 

#스택  

 

 

🤯 풀이 방법

마지막 인덱스부터 거꾸로 탐색하며 최대값을 저장한다.
위에서부터 차례로 꺼내며 더 큰 값을 찾으면 그 값이 오큰수
현재 인덱스의 값이 다른 수의 오큰수가 될 수 있기 때문에 현재 인덱스의 값도 저장
후보 리스트의 값을 모두 꺼내도 답을 찾지 못한 경우 답은 -1
⚠ 마지막 인덱스부터 거꾸로 도는 방법이 좋은 것 같지는 않은데 이게 최선인가?

 

👾 구현 코드 (파이썬)

# [BOJ] 17928. 오큰수
import sys
input = sys.stdin.readline
N = int(input())
L = list(map(int, input().split()))
T = []  # 현재 가능한 경우의 수 (높은 값들) 저장
A = []  # 정답 저장할 리스트
for i in range(N - 1, -1, -1):  # 마지막부터 탐색
    if len(T) == 0:   # 더 높을 수 있는 경우의 수가 없는 경우 -1
        A.append(-1)
        T.append(L[i])  # 현재 값 후보로 저장

    else:
        while T and T[-1] <= L[i]:  # 더 큰 값을 찾을 때까지 후보 없애버림
        while T and T[-1] <= L[i]:  # 더 큰 값을 찾을 때까지 후보 목록에서 삭제하며 확인
            T.pop(-1)
        if T:
            A.append(T[-1])   # 찾으면 마주한 값을 답에 추가
        else:
            A.append(-1)  # 후보중에 더 큰 값이 없으면 -1
        T.append(L[i])  # 현재 내 값도 후보에 부조건 추가
        T.append(L[i])  # 현재 내 값도 후보에 무조건 추가

for i in range(N - 1, -1, -1):  # 답 순서 반대로 출력
    print(A[i], end=" ")

 

 

 

17298번: 오큰수