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

오큰수 - 17298

문제 링크

17298번: 오큰수

성능 요약

메모리: 155576 KB, 시간: 1140 ms

분류

자료 구조, 스택

문제 설명

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

---

🙋 문제 해석

일단 이 문제는 오른쪽에서 가까운 수 중 가장 큰 수를 스택에 넣어서 해결 하는 문제입니다. 완전탐색으로 풀면 O(n^2) 시간초과가 나옵니다. (완전탐색은 대략, 20초 더 나오는듯)

 

 

입력값이 n<1,000,000 이기 때문에 최대한 O(n)으로 풀어야합니다.

 

일단 최대한 선형으로 풀기 위해서는, 한 번에 끝내야 하는데요, 이를 위한 방법이 인덱스를 저장하면 됩니다.

차근차근 설명해보겠습니다!!

 

 

 

예를들어서

Step 1 인덱스를 저장하기

stack = [] # 인덱스를 저장할 스택

for i in range(2):
  stack.append(i)

이런 코드가 있다고 생각해봅시다.

Step 2 저장한 인덱스와 현재 비교

lis = [3,1,6,7]
stack # 스택에는 인덱스가 들어있음 [0,1]

lis[2] > lis[stack[-1]] # 6 > 1 --> True입니다.

여기 까지 lis[2] = 6 lis[stack[-1]] = 1 입니다.

Step 3 뺀 뒤에 반복

lis[2] > lis[stack[-1]] # 6 > 1 --> True
stack.pop()
lis[2] > lis[stack[-1]] # 6 > 3 --> True

여기 까지만 이해하면 됩니다.

 

코드를 살펴보겠습니다.

---

🔑 Solution 🔑

N = int(input())
lis = list(map(int,input().split()))
result = [-1] * N
stack = []
for i in range(N):
    while stack and lis[i]>lis[stack[-1]]: # Step 2부분

        result[stack[-1]]=lis[i] # Step 2 부분

        stack.pop() # Step 3 부분

    stack.append(i) # Step 1 부분
print(*result)

• 스택에 인덱스를 저장합니다.
• 스택의 마지막 인덱스가 현재 인덱스의 값보다 작은 경우, 스택에서 마지막 인덱스를 꺼내서 해당 인덱스의 결과 값을 현재 인덱스의 값으로 갱신합니다.
• 스택에서 마지막 인덱스를 꺼냅니다.

---

🕐 시간 복잡도

스택 연산의 시간 복잡도는 상수 시간( O(1) )으로 간주할 수 있으므로, 전체적인 시간 복잡도는 O(N)입니다.

---

다른 쉬운 스택 문제들

[백준][10845][Silver 4] - 큐 python

[백준][17413] - 단어 뒤집기 2 python 파이썬

 

🙇