[백준 17298번] 오큰수

[백준 17298번] 오큰수

• 문제 링크 : 수 찾기
• 난이도 : 골드 4
• 풀이 날짜 : 2025-02-04

---

📖 문제 설명

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

⌨️ 예제 입출력

입력

4
3 5 2 7

출력

5 7 7 -1

---

📝 풀이 코드

from collections import defaultdict, deque
import sys
input = sys.stdin.readline

N = int(input())  # 배열 크기
numbers = list(map(int, input().split()))  # 숫자 리스트

result = [-1] * N  # 기본값 -1로 초기화
stack = []  # 인덱스를 저장하는 스택

for i in range(N):
    while stack and numbers[stack[-1]] < numbers[i]:  # 현재 숫자가 스택 top보다 크다면
        result[stack.pop()] = numbers[i]  # 스택에서 pop하고 오큰수로 저장
    stack.append(i)  # 현재 인덱스 저장

print(*result)  # 결과 출력 (공백으로 구분)

---

🔍 코드 설명

• 배열의 크기와 숫자 리스트를 입력 받는다.
• 결과 리스트를 -1로 초기화
• 스택 생성(list)
• 배열의 크기만큼 반복문 실행
• 스택에 인덱스 저장
  • 만약 스택이 비어있지 않고, 현재 숫자가 스택의 top보다 크면 스택에서 빼고 오큰수로 저장
• 결과를 언패킹으로 출력