백준 - 17299 오등큰수 (파이썬)

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

문제풀이

---

문제 정리

• Ai가 수열 A에서 등장한 횟수를 F(Ai)라고 했을 때, Ai의 오등큰수는 오른쪽에 있으면서 수열 A에서 등장한 횟수가 F(Ai)보다 큰 수 중에서 가장 왼쪽에 있는 수를 의미한다. 그러한 수가 없는 경우에 오등큰수는 -1이다.

분석

👓 분석하기 앞서
해당 문제는 오큰수 풀이와 유사하다. 이전 문제를 잘 분석하고 적용할 수 있는지 확인하기위해 풀어보았다.

1. 숫자가 등장한 횟수를 비교해야하기 때문에 메모리에 등장횟수를 저장해놓을 수 있다.

   100만개의 데이터를 리스트에 저장하면 4MB 정도의 메모리가 소요된다. 문제에서는 메모리 제한이 512MB이기 때문에 여유로울 것이다.

   count = [0] * 1000001
    stack = []
    res = [-1] * N
    for num in seq:
        count[num] += 1
       .
       .

2. i번째 값을 오등큰수로 하는 수들은 무엇일까

   오큰수 문제와 마찬가지로 i번째 값을 오등큰수로 하는 수들은 스택에 저장할 수 있다.

3. for 문을 돌며 현재 숫자의 카운트와 스택의 카운트를 비교하며 결과를 업데이트 할 수 있다.

시간복잡도

• 시간복잡도는 $O(n)$ 이다
• count 업데이트 (100만) + for문 (100만) + 스택 비교 (100만) = 300만으로 여유로울 것이다.

전체코드

---

N = int(input())
seq = list(map(int, input().split()))

count = [0] * 1000001
stack = []
res = [-1] * N
for num in seq:
    count[num] += 1

for i in range(N):
    while stack and count[seq[stack[-1]]] < count[seq[i]]:

        res[stack.pop()] = seq[i]
    stack.append(i)

print(" ".join(map(str,res)))

정리 및 느낀점

---

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

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

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