[파이썬(Python)] 백준 17299번 오등큰수

 

 

백준 17299번: 오등큰수

문제 바로 가기

---

📌 문제

크기가 N인 수열 $A = A_1, A_2, ..., A_N$이 있다. 수열의 각 원소 Ai에 대해서 오등큰수 NGF(i)를 구하려고 한다.

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

예를 들어, $A = [1, 1, 2, 3, 4, 2, 1]$인 경우 $F(1) = 3$, $F(2) = 2$, $F(3) = 1$, $F(4) = 1$이다. $A_1$의 오른쪽에 있으면서 등장한 횟수가 3보다 큰 수는 없기 때문에, $\text{NGF}(1) = -1$이다. $A_3$의 경우에는 $A_7$이 오른쪽에 있으면서 $F(A_3=2) < F(A_7=1)$ 이기 때문에, $\text{NGF}(3) = 1$이다. $\text{NGF}(4) = 2$, $\text{NGF}(5) = 2$, $\text{NGF}(6) = 1$이다.

 

입력
첫째 줄에 수열 $A$의 크기 $N (1 ≤ N ≤ 1,000,000)$이 주어진다.
둘째 줄에 수열 $A$의 원소 $A_1, A_2, ..., A_N (1 ≤ Ai ≤ 1,000,000)$이 주어진다.

 

출력
총 $N$개의 수 $\text{NGF}(1), \text{NGF}(2), ..., \text{NGF}(N)$을 공백으로 구분해 출력한다.

 

 

 

📝 문제 접근 방법

 

• 문제 분석
  • 주어진 수열에서 각 원소에 대해  현재 숫자보다 오른쪽에 있으면서 현재 숫자의 등장 횟수보다 더 많이 등장한 숫자 중 가장 왼쪽에 있는 숫자인 오등큰수(NGF)를 찾아야 합니다.
  • 특정 원소에 대해 조건에 맞는 오등큰수가 존재하지 않으면 -1로 표기합니다.

 

• 아이디어
  1. 등장 횟수 계산
     • 주어진 수열에서 각 숫자가 몇 번 등장하는지를 계산해두면 각 숫자의 오등큰수를 결정할 때 등장 횟수를 빠르게 비교할 수 있습니다.
  2. 스택을 이용하여 오등큰수 찾기
     • 오른쪽에 있는 숫자 중에서 등장 횟수가 더 많은 숫자를 찾아야 하므로 왼쪽에서 오른쪽으로 수열을 순회하면서 오둥큰수를 탐색합니다. 

 

• 예제: $A = [1, 1, 2, 3, 4, 2, 1]$

 

 

 

👩‍💻 나의 답안

import sys 
input = sys.stdin.readline

n = int(input())
arr = list(map(int, input().split()))

frequency = {}
for num in arr:
    frequency[num] = frequency.get(num, 0) + 1 

result = [-1] * n
stack = []

for i in range(n):
    while stack and frequency[arr[stack[-1]]] < frequency[arr[i]]:
        index = stack.pop()
        result[index] = arr[i]
    stack.append(i)

print(*result)