[백준 17299 파이썬] 오등큰수 (골드 3, 스택)

알고리즘 유형 : 스택
풀이 참고 없이 스스로 풀었나요? : O

https://www.acmicpc.net/problem/1912

소스 코드(파이썬)

import sys
input = sys.stdin.readline

N = int(input())
A = [*map(int, input().split())]
F_dict = dict()

for n in A:
    if not F_dict.get(n):
        F_dict[n] = 1
    else:
        F_dict[n] += 1

F_A = [(F_dict[A[i]], A[i]) for i in range(len(A))]
NGE = [-1]
stack = [F_A[-1]]

for i in range(-2, -1*N-1, -1):
    while stack:
        if F_A[i][0] < stack[-1][0]:
            NGE.append(stack[-1][1])
            break
        else:
            stack.pop()
    
    if not stack:
        NGE.append(-1)
    
    stack.append(F_A[i])

print(*NGE[::-1])

풀이 요약

1. 문제를 먼저 분석해보자. A(i)의 오등큰수는 A의 오른쪽에 있는 수들중에, A에서의 A(i)의 등장횟수보다 더 등장횟수가 많은 수들 중 가장 왼쪽의 수이다.

   이러한 오등큰수를 A의 모든 원소에 대해 구하는 것이 목표이다.

   그런데 잘보면 오등큰수의 정의에서 활용되는 수는 숫자들의 등장횟수들 뿐이다. A의 원본 숫자들은 그저 그 등장횟수를 구할 때 쓰일뿐이다.

   즉, 수들의 등장횟수로 구성된 새로운 배열 F_A를 만들어보자.

2. count로 매번 계산해주면 O(N^2)가 소요되어 비효율적이다. dict로 구해보자.

   A를 순회하면서 dict에 값을 카운팅해둔다.

   새로운 배열에 값을 추가할 때는 그저 그 인덱스에 해당하는 A의 원소로 dict를 인덱싱해온 값을 추가하기만 하면 된다.

   이렇게 하면 O(N)이다.

3. 이렇게 새로운 배열을 만들고나면 오큰수 문제 풀이와 거의 동일해진다.

   조금 다른점은, 오큰수를 저장할 때(결과값) 등장횟수가 아닌, 원래 A의 원본 숫자를 저장해둔 뒤 출력해줘야한다는 점이다.

   등장횟수로 치환해서 문제를 푼 것이니 당연히 결과를 출력할 때는 원래 수로 돌려줘야한다.

   이를 위해, stack에 등장횟수와 더불어 원래의 수를 튜플로 묶어 저장한다.

   순회중인 특정 등장횟수 숫자에 대해 오큰수가 확정되면, 그 때 튜플로 묶어둔 원래 수를 NGE에 저장해두기만 하면 된다.

배운 점, 어려웠던 점

• 사실상 문제의 조건을 적당히 치환해서 단순화시키고 오큰수 문제로 바꿔푸는 문제였다. 어렵지 않은 문제였다.