[백준 17299] 오등큰수

문제

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

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

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

 

입력

첫째 줄에 수열 A의 크기 N (1 ≤ N ≤ 1,000,000)이 주어진다. 둘째에 수열 A의 원소 A1, A2, ..., AN (1 ≤ Ai ≤ 1,000,000)이 주어진다.

 

출력

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

---

접근

각 숫자가 몇 번 나오는지 계산하여 counter 리스트에 저장하고 해당 인덱스에 있는 수와 count를 짝지어서 새로운 리스트를 생성한다. 이후 새롭게 생성한 리스트와 스택을 활용하여 문제에서 원하는 해를 구하도록 한다.

 

구현

- 입력받은 숫자들의 빈도 수를 계산하여 counter리스트에 저장한다.

- 이제 각 인덱스에 해당되는 숫자와 count를 튜플 형태로 짝 지어서 새로운 리스트에 저장한다.

for number in numbers:
    counter[number] += 1

number_counter_list = []
for number in numbers:
    number_counter_list.append((number, counter[number]))

- 반대에서부터 탐색을 진행한다.

- 스택이 비어있을 때 현재의 숫자와 count를 스택에 저장하고 

- 최종해를 담는 리스트에는 -1을 추가한다.

- 스택의 top에 있는 count가 현재 count보다 크다면 최종해에 스택의 top에 있는 숫자를 추가하고

- 스택에 현재 숫자와 count를 추가한다.

- 그렇지 않다면 큰 것이 나올 때까지 whlie문을 통해 스택을 pop한다.

- pop 이후에 스택이 비어있다면 최종해에 -1을 추가하고 아니라면 top에 있는 숫자를 추가한다.

- 그리고 위와 마찬가지로 현재 숫자와 count를 스택에 추가한다.

for number, counter in reversed(number_counter_list):
    if stack:
        if stack[-1][1] > counter:
            answer.append(stack[-1][0])
            stack.append((number, counter))
        else:
            while stack and stack[-1][1] <= counter:
                stack.pop()
            if stack:
                if stack[-1][0] == number:
                    answer.append(-1)
                else:
                    answer.append(stack[-1][0])
            else:
                answer.append(-1)
            stack.append((number, counter))
    else:
        stack.append((number, counter))
        answer.append(-1)

---

전체 코드

import sys
input = sys.stdin.readline

N = int(input())
numbers = list(map(int, input().split()))
counter = [0] * (max(numbers) + 1)
for number in numbers:
    counter[number] += 1

number_counter_list = []
for number in numbers:
    number_counter_list.append((number, counter[number]))

stack = []
answer = []

for number, counter in reversed(number_counter_list):
    if stack:
        if stack[-1][1] > counter:
            answer.append(stack[-1][0])
            stack.append((number, counter))
        else:
            while stack and stack[-1][1] <= counter:
                stack.pop()
            if stack:
                if stack[-1][0] == number:
                    answer.append(-1)
                else:
                    answer.append(stack[-1][0])
            else:
                answer.append(-1)
            stack.append((number, counter))
    else:
        stack.append((number, counter))
        answer.append(-1)

answer = list(reversed(answer))
print(*answer)