백준 알고리즘 - 오큰수 (17298) [Python]

 

 

 문제

 

www.acmicpc.net/problem/17298

17298번: 오큰수

 

 

 

 

 

 

 문제 상황

 

- 배열 A가 주어지고 특정 인덱스 i를 기준으로 i보다 큰 수 중 A[i]<A[k] 이며 최소가 되는 k를 찾아 result[i]에 A[k]를 저장하여 출력하는 문제이다.

 

 

 

 

 

 

 해결 전략

 

- 백준의 탑 문제와 흡사한 문제로 stack을 활용하여 왼쪽을 쳐다보게 하는 문제이다. 즉, 문제의 조건처럼 오른쪽으로 더 큰 방향을 관찰하는게 아니라 더 커지는 기준 수를 기준으로 왼쪽을 봐서 가장 작은 경우를 출력하는데, 이 때 stack은 내림차순을 유지하여 마지막 수와 비교하여 추가하는 식으로 풀이를 진행한다. 즉, 가장 포인트가 되는 것은 stack을 내림차순으로 유지하여 기준 수가 더 큰 경우는 전부 pop하여 저장하고, 내림차순이 유지되면 추가하고 다음으로 넘어가는 방식이다.

 

 

 

 

 

 

 코드

 

from sys import stdin
 
input = stdin.readline
stack = [0]
n = int(input())
result = [-1 for _ in range(n)]
A = list(map(int, input().strip().split()))
for i in range(1, n):
    while stack and A[stack[-1]] < A[i]:
        result[stack.pop()] = A[i]
    stack.append(i)
print(' '.join(map(str, result)))

 

 

 

 

 

 

 새로 학습한 것 & 실수 

 

- 내림차순을 유지한다는 개념 하나만 빠져도 위의 코드는 O(N^2)가 되어 시간 초과가 발생한다. 문제의 포인트는 기준점을 반대로 잡아 내림차순을 유지하며 왼쪽을 쳐다보게 하는 것이다.