[Python 파이썬]백준 17298번 - 오큰수

2023년 9월 27일

문제 링크 : 백준 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)을 공백으로 구분해 출력한다.

 

알고리즘 분류

• 자료 구조
• 스택

---

문제 접근

특정 정수보다 큰 수가 오른쪽에 위치해있다면, 가장 가까이 위치해 있는 정수가 특정 정수의 오큰수이다.

무식하게 접근하자면 특정 정수의 오큰수를 확인할 때 오른쪽에 있는 모든 정수들을 하나씩 확인해봐야 하지만,

원소의 개수가 10의 6승이라 그리디하게 접근하면 시간초과가 날 것 같았다.

시간복잡도를 O(n)으로 코드를 설계하고 짜야하는데 어떻게 해야할까 고민하다 스택을 이용해 접근해보기로 했다.

---

순서도

1. 입력값을 입력받아 리스트에 저장한다.

2. 결과를 출력하기위한 리스트를 생성한다. 크기는 입력받는 정수의 개수와 같은 N. 초기값은 -1
	초기값을 -1로 두는 이유는 오큰수가 없는 정수의 경우 -1을 출력하기 때문.
    
3. 스택 자료구조를 위한 리스트 선언

4. 입력값으로 받은 정수들이 담겨있는 리스트를 0번째 인덱스부터 차례로 순회하며 반복문을 진행한다.

5. 만약 스택에 아무것도 담겨있지 않다면 현재 순회한 정수를 스택에 담는다.
	만약 스택에 요소가 담겨있다면 스택의 가장 마지막 인덱스 위치의 값이 현재 순회한 정수보다 작은지 확인한다.

6. 만약 작다면 현재 인덱스 번호보다 1 작은 인덱스 번호를 따로 저장해두고, 스택 마지막 요소가 현재 순회한 정수보다 작은 수가 없을 때까지 반복문을 진행한다.
	현재 순회한 정수보다 작은 정수가 스택에 담겨있다는 의미이니, 스택 요소를 pop하며 해당 정수의 오큰수를 현재 순회한 정수로 지정한다.

7. 5~6번 과정을 계속 진행하면 스택에 담긴 요소들은 현재 순회한 정수보다 큰 수만 남게 된다.
	입력값이 담겨 있는 리스트를 끝까지 순회한 후, 결과값을 출력한다.

---

입력 예제

4
3 5 2 7

 

입력값 list에서 0번째 인덱스 순회

현재 순회한 인덱스의 정수는 3이다.

스택의 마지막 값과 비교하려 했으나, 스택이 비어있기에 현재 순회 정수인 3을 그대로 스택에 append한다.

 

 

 

입력값 list에서 1번째 인덱스 순회

현재 순회한 정수는 5이다.

스택의 마지막 값과 비교하니 현재 순회 정수가 더 큰 것을 확인할 수 있다.

이는 스택의 마지막 값의 오큰수(오른쪽에 존재하는 자신보다 큰 수 중, 가장 가까이 있는 수)는 현재 순회 정수라는 뜻이다.

스택의 마지막 값의 오큰수가 현재 순회 정수임을 확인했으니, pop하여 마지막 값을 빼내어 준다.

그리고 해당 정수의 오큰수를 기입하기 위해, 오큰수 list의 해당 정수 인덱스 번호에 현재 순회 정수를 기입하여 준다.

 

 

위 과정을 거치고 나니 스택에 더 이상 비교할 수 있는 값이 존재하지 않기에, 현재 순회 정수를 스택에 append한다.

 

입력값 list에서 2번째 인덱스 순회

 

현재 순회한 정수는 2이다.

스택의 마지막 값과 비교해보니 현재 순회 정수가 더 작다.

현재 순회 정수를 그대로 스택에 append한다.

 

 

입력값 list에서 3번째 인덱스 순회

현재 순회한 정수는 7이다.

스택의 마지막 값은 2 이므로 현재 순회 정수가 더 크다는 것을 확인하였다.

그러므로, 스택의 마지막 값을 pop하고, 오큰수 list에서 pop한 정수 인덱스 위치에 오큰수를 기입하여 준다.

 

스택에 값이 남아있으니, 더 확인해준다.

스택의 마지막 값은 5이므로 현재 순회 정수가 더 크다는 것을 확인하였다.

그러므로, 스택의 마지막 값을 pop하고, 오큰수 list에서 pop한 정수 인덱스 위치에 오큰수를 기입하여 준다.

 

스택에 더 비교할 값이 없으므로, 현재 순회 정수를 append한다.

 

 

입력값 list 내의 모든 요소 순회를 마쳤다.

이 문제가 원하는 해답인 오큰수 list를 출력한다.

 

출력 예제

5 7 7 -1

---

주의할 점

결과값 출력할 때, 리스트 자체를 바로 출력하는 것이 아닌, 요소와 요소 사이에 띄어쓰기가 존재하는 한 줄 형태로 출력해야 함에 유의한다. ( 리스트 자체를 그대로 출력했다가 틀렸습니다! 당했다.. )

---

전체 코드

# 17298

import sys
input = sys.stdin.readline

if __name__ == "__main__":
    N = int(input())

    arr = list(map(int, input().split()))
    result = [-1] * N

    stack = []
    for idx in range(N):
        if stack:
            if stack[-1] < arr[idx]:
                _idx =  idx - 1
                while stack and stack[-1] < arr[idx]:
                    if _idx >= 0 and result[_idx] == -1:
                        stack.pop()
                        result[_idx] = arr[idx]
                    _idx -= 1
        
        stack.append(arr[idx])
    
    for n in result:
        print(n, end=" ")

---

풀이 후기

시간복잡도가 O(n)인 코드로 설계하기 위해 구상하는 과정에서 스택을 사용해야겠다 라는 결과 도출까지가 이 문제의 핵심인듯 싶다.