백준 17298 | 오큰수 | python 풀이

문제

https://www.acmicpc.net/problem/17298

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이다.

 

내 답안

# 17298 오큰수
import sys as s

n = int(s.stdin.readline().strip())
nums = list(map(int, s.stdin.readline().split()))
stack = []
nge = [-1] * n

for i in range(n):
  while stack and nums[stack[-1]] < nums[i]:
    nge[stack.pop()] = nums[i]

  stack.append(i)

print(*nge)

해설

스택을 활용하는 문제다.

백준 6198 옥상정원꾸미기 문제와 접근방법이 굉장히 유사하다.

해당 문제의 풀이는 여기를 참고하면 좋을 것이다!

 

접근법은 수열 nums에 들어있는 원소들을 순회하면서 'stack안의 원소 중, 나를 NGE로 하는 원소'를 찾는 것이다. 그리고 stack에는 원소의 인덱스를 저장해야 시간복잡도를 맞출 수 있다. 원소 값을 저장하면, index() 메서드로 인덱스를 찾는 데 O(n)  시간이 걸리기 때문에 바로 시간초과 난다.😂

 

 

stack 유형만 집중적으로 계속해서 풀다보니까 어떻게 접근해야 할 지 감이 잡히는 듯 하다!

 

피드백

• stack에 원소를 넣을 수도 있지만, 인덱스를 넣을 수도 있다.
  • 인덱스를 찾는 연산인 index()가 시간복잡도 O(n) 이기 때문에 사용에 유의하자