[백준 17298 파이썬] 오큰수 (골드 4, 스택)

알고리즘 유형 : 스택
풀이 참고 없이 스스로 풀었나요? : O

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

소스 코드(파이썬)

import sys
input = sys.stdin.readline

N = int(input())
A = [*map(int, input().split())]
NGE = [-1]
stack = [A[-1]]

for i in range(-2, -1*N-1, -1):
    is_exist = False
    while stack:
        if A[i] < stack[-1]:
            NGE.append(stack[-1])
            is_exist = True
            break
        else:
            stack.pop()
    
    if not is_exist:
        NGE.append(-1)
    
    stack.append(A[i])

print(*NGE[::-1])

풀이 요약

1. A(i)의 오큰수는 A(i)의 오른쪽에 있는 수들 중 하나로 결정되거나 -1로 결정된다.

   즉, 초기 탐색을 A의 가장 오른쪽부터 탐색하는 방식으로 생각해보자.

   
   

   예제 3 5 2 7을 예로 들어보자.

   우선 맨 오른쪽의 오큰수는 항상 -1이다.

   7이 왼쪽의 어떤 수의 오큰수가 될 수 있으니 일단 리스트에 저장해두자.

   
   

   3 5 2 7

   2와 리스트에 저장된 7을 비교해보자. 2의 오큰수는 7이다.

   이 2도 왼쪽의 어떤 수의 오큰수일 수도 있으니 리스트에 저장해두자.

   
   

   3 5 2 7

   다음은 5이다. 여기서 오큰수를 따질 때 리스트에 저장해 둔 값 중, A에서 5에 가장 가까이 있는 수들 순으로 검사해야한다. 오큰수의 정의 자체가 자신보다 오른쪽에 있고 값이 더 큰 수들 중, 자신과 가장 가까운 수이기 때문이다.

   일단 2와 비교해보면 오큰수가 아니다. 이 때 2를 리스트에서 지워주자. 왜냐하면 2는 5 왼쪽에 있는 모든 수들에 대해 오큰수가 될 수 없기 때문이다.

   만약 5 왼쪽에 있는 수들 중에 자신의 오큰수가 2인 수 k가 있다고 가정해보자.

   이 말은 곧 k가 2보다 작다는 뜻인데, 이 때 k는 5와 비교했을 때 당연히 더 작다.

   그런데 5가 2보다 k에 더 가까이있으니 k의 오큰수는 5가 되어야하므로 모순이다.

   
   

   앞서 탐색한 수들을 리스트에 저장해둔다고 했는데, 수를 계속 탐색해가면서 리스트에서 수를 꺼내 오큰수인지를 판별할 때, 이 꺼내는 수는 현재 탐색 중인 수 k에 가장 가까운 수부터 꺼내야한다.

   이 말은 곧 리스트에 가장 최근에 넣은 수부터 먼저 비교해야한다는 뜻이니, 스택의 특성과 똑같다. 스택을 활용하자.

2. 요약하면,

   1) A의 맨 오른쪽부터 왼쪽 방향으로 순회하기

   2) 현재 순회중인 수 k와 스택의 원소들을 비교하면서 오큰수 찾기(오큰수가 아닌 스택의 원소는 곧바로 pop해서 지워주기.), 없으면 오큰수는 -1임

   3) k를 스택에 넣어두기(왼쪽의 어떤 수의 오큰수가 될 수도 있는 수임)

   4) 끝까지 반복

배운 점, 어려웠던 점

• 문제의 조건을 분석하고 규칙을 파악하면서 예제를 따라가다보면 스택의 활용 구조가 보이는 문제였다. 차근차근 단계적으로 분석해나가는게 중요한 것 같다.