[백준 17298] 오큰수

문제

크기가 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)을 공백으로 구분해 출력한다.

---

접근

처음에 왼쪽부터 순차적으로 탐색하여 설계를 하였을 때 오큰수를 찾을 수 없었다. 이전의 기록들을 살펴보면서 해를 구해야하는데 왼쪽부터 탐색을 진행하면 스택을 사용하는 장점이 사라졌다.

예를 들어 3 5 2 7이 있을 때 5의 오큰수는 7인 것을 찾았다면 이제 2의 오큰수를 찾아야하는데 탐색이 7까지 진행되어 다시 이전으로 돌아가야하는 문제가 생겼다.

 

따라서 오른쪽부터 탐색을 진행하였다. 가장 오른쪽에 있는 숫자는 무조건 -1이다. 

이후 계속해서 스택에 숫자를 넣고 스택의 top과 현재 수를 비교했을 때 스택의 top이 더 크다면 현재 숫자의 오큰수는 스택의 top이된다.

하지만 현재 숫자가 더 크다면 스택을 계속 pop하여 오큰수를 찾는다. 스택에는 현재 숫자에서 왼쪽부터 저장되어있기 때문에 큰 수를 찾았다면 종료하고 해당 수를 오큰수로 정한다.

 

구현

- 스택이 비어있다면 오큰수가 없다는 것이기 때문에 최종해에 -1을 추가하고

- 스택에 현재 숫자를 추가한다.

- 그리고 스택의 top과 현재 숫자를 비교한다.

- 스택의 top이 크다는 것은 현재 숫자의 오큰수이기 때문에 스택의 top을 최종해에 추가하고

- 현재 숫자를 스택에 넣는다.

- 스택의 top이 더 작다면 오큰수를 pop하면서 찾는다.

- while문을 통해 오큰수를 찾기위한 탐색을 완료했을 때 stack이 비게된다면 -1을 넣고 아니라면 스택의 top을 최종해에 추가한다.

for number in reversed(numbers):
    if stack:
        if stack[-1] > number:
            answer.append(stack[-1])
            stack.append(number)
        else:
            while stack and stack[-1] <= number:
                stack.pop()
            if stack:
                answer.append(stack[-1])
            else:
                answer.append(-1)
            stack.append(number)
    else:
        answer.append(-1)
        stack.append(number)

---

전체 코드

import sys
input = sys.stdin.readline

N = int(input())
numbers = list(map(int, input().split()))
stack = []
answer = []
for number in reversed(numbers):
    if stack:
        if stack[-1] > number:
            answer.append(stack[-1])
            stack.append(number)
        else:
            while stack and stack[-1] <= number:
                stack.pop()
            if stack:
                answer.append(stack[-1])
            else:
                answer.append(-1)
            stack.append(number)
    else:
        answer.append(-1)
        stack.append(number)

answer = list(reversed(answer))
print(*answer)