백준 - 17298 오큰수 (파이썬)

문제 링크 : https://www.acmicpc.net/problem/17298
난이도 : 골드 4

문제풀이

---

문제 정리

• 오큰수는 오른쪽에 있으면서 Ai보다 큰 수 중에서 가장 왼쪽에 있는 수를 의미한다. 그러한 수가 없는 경우에 오큰수는 -1이다.

분석

1. 순서대로 확인하는 방법을 사용할 수 있다. 현재 수에서 뒷쪽에 있는 수들 중 큰 수를 발견하면 continue 한다고 생각해 볼 수 있다.

   이러한 방식의 접근은 배열이 내림차순일때 $O(n^2)$ 인 시간복잡도가 나와 시간초과를 야기할 것이다.

   $O(n)$ 혹은 $O(nlogn)$ 정도가 되어야 문제를 풀 수 있을것이다.

2. 문제가 잘 안 풀릴 때는 기준을 뒤집어 생각해 볼 필요가 있다. 현재 수의 오큰수를 구하는 것보다 현재 수가 누군가의 오큰수일 수도 있다고 생각할 수 있다.

3. 누군가의 오큰수에서 "누군가" 들을 스택에 넣어놓으면 좋을 것이다.

4. 오큰수를 못 찾은 수들이 "누군가" 이므로 스택에 들어갈 후보가 된다.

5. 후보는 인덱스로 저장해야 추후에 업데이트 할 수 있을 것이다.

   오큰수를 못 찾은 수들은 어떻게 저장할 수 있을까?

   • 오큰수를 찾지 못한 수는 추후에 업데이트 하면된다.
   • 추후 에 업데이트 하면 되기 때문에 스택에 저장하면 된다.
   • 추후에 저장하기 위해서는 인덱스를 스택에 저장해야한다.

     for i in range(N):
     	.
         .
     	# 오큰수를 찾지 못해 추후에 업데이트 필요한 수들을 스택에 담음
         stack.append(i)

   현재 수가 누군가의 오큰수일 수도 있다

   for i in range(N):
   	# 오큰수 업데이트 : 스택에 있는 후보들을 전부 업데이트 가능한 지 확인
       # 현재 인덱스인 수보다 작다면 업데이트 가능
       # 업데이트 가능하면 스택을 pop 하고 결과에 오큰수를 저장한다
       while stack and sequence[stack[-1]] < sequence[i]:
       	index = stack.pop()
   		      	result[index] = sequence[i]
       .
       .

시간복잡도

• 시간복잡도는 $O(n)$ 이다
• 200만 정도로 충분히 여유있을거라 예상된다.

전체코드

---

N = int(input())
seq = list(map(int, input().split()))
stack = []
res = [-1] * N

for i in range(N):
    while stack and seq[stack[-1]] < seq[i]:
        res[stack.pop()] = seq[i]
    stack.append(i)

print(res)

정리 및 느낀점

---

• for문을 돌때 현재 위치에서 부터의 값을 구하기 어려우면, 현재 위치는 누군가의 값이 될까? 생각해볼 수 있다.

  i번째 값에서 오큰수는 무엇일까? vs i번째 값을 오큰수로 하는 수들은 무엇일까?

• 스택 은 LIFO로 선입후출이라는 특징도 가지고 있지만, 후보군으로 담고 있다가 늦은 업데이트를 할 때도 유용할 수 있다.