[92일차][백준][자료구조, 스택][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)을 공백으로 구분해 출력한다.

 

예제 입력, 예제 출력

7 1 1 2 3 4 2 1

-1 -1 1 2 2 1 -1

 

코드 및 설명

import sys
from collections import Counter

n = int(sys.stdin.readline())
n_arr = list(map(int, sys.stdin.readline().strip().split(" ")))
f_stack = Counter(n_arr)
ngf_stack = []
answer = [0] * n

for i, val in enumerate(n_arr):  
  while ngf_stack and f_stack[n_arr[ngf_stack[-1]]] < f_stack[val]:   
    answer[ngf_stack.pop()] = val
                
  ngf_stack.append(i)
  
if ngf_stack:
  for val in ngf_stack:
    answer[val] = -1
    
print(" ".join(str(val) for val in answer))

 

이 문제는 저번에 풀었던 오큰수에서 변형이 들어간 문제이다. 문제에서 보면 

 

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

 

일단 여기서 보면 수열 A에서 Ai가 등장한 횟수 이게 첫번째 해야할 작업.

 

1 1 2 3 4 2 1

 

여기 예제를 보면 1이라는 수가 들어오면 이게 전체 수열에서 1이 몇 개 있는 지를 먼저 알아야 문제를 풀 수 있다.

 

지금 수가 몇개 안되니 눈으로 보면 1 = 전체 수열에서 3개를 가지고 있다. 등장횟수가 3이고 이것보다 큰 등장 횟수를 가

 

진 수열은 없다. 그러니 -1이 된다.

 

먼저 전체 수열에 각각의 등장횟수를 먼저 구해줘야하는 데 collections 모듈을 이용했고,  밑에 코드를 보면 직접한 것도

 

있다. 둘 다 통과된다.

 

Counter(n_arr)를 넣으면 Counter({1: 3, 2: 2, 3: 1, 4: 1}) 이렇게 만들어준다.

 

f_stack이라고 정한건 F(Ai)라고 해서 f_stack으로 붙여줬다. 하이튼 이렇게 만들었으면 첫번째 작업은 완료다.

 

두번째로 오등큰수를 구해야한다. 이거는 거의 오큰수(백준 17298 )와 흡사하다. 아니? 같다고 해야하나 하이튼

 

처음은 ngf_stack 쌓인게 없기 때문에 쌓아주고, 

 

while에서 ngf_stack 있거나, f_stack top보다 f_stack[n_arr의 val]가 크면 오등큰수는 f_stack top의 위치값에

 

val를 넣어주면 된다. 이걸 끝날때까지 반복

 

이후에 ngf_stack이 비어있지 않으면 이 위치값들의 오등큰수는 없는거다. 그러므로 -1을 넣어주면 된다.

 

import sys

n = int(sys.stdin.readline())
n_arr = list(map(int, sys.stdin.readline().strip().split(" ")))
f_stack = {}

for i, val in enumerate(n_arr):
  if val in f_stack.keys():
    f_stack[val] += 1
  else:
    f_stack[val] = 1
    
ngf_stack = []
answer = [0] * n

for i, val in enumerate(n_arr):  
  while ngf_stack and f_stack[n_arr[ngf_stack[-1]]] < f_stack[val]:   
    answer[ngf_stack.pop()] = val
                
  ngf_stack.append(i)
  
if ngf_stack:
  for val in ngf_stack:
    answer[val] = -1
    
print(" ".join(str(val) for val in answer))