[BaekJoon] 17299 오등큰수 (Gold 3) - Python

문제

 

크기가 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)을 공백으로 구분해 출력한다.

 

입력예시1)

7
1 1 2 3 4 2 1

출력예시1)

-1 -1 1 2 2 1 -1

---

코드

 

import sys
input = sys.stdin.readline # 빠른 입력 on

N = int(input()) # N입력
num = list(map(int, input().rstrip().split())) # 숫자 입력
result = [-1 for _ in range(N)] # 결과값 리스트 생성
cnt = [0 for _ in range(max(num) + 1)] # 각 원소가 나온 횟수를 카운트 하기 위한 리스트 생성
for i in num: cnt[i] += 1 # 원소 개수 카운트
stack = [] # 사용할 스택 선언

for i in range(N): # 반복
    while stack and (cnt[stack[-1][0]] < cnt[num[i]]): # 스택이 비어있지 않고, 스택 맨 위의 원소가 나온 횟수가 현재 원소가 나온 횟수보다 작으면
        tmp, idx = stack.pop() # 스택 맨 위의 값을 pop하고
        result[idx] = num[i] # 결과값 리스트에 반영한다
    stack.append([num[i], i]) # 스택에 현재 원소의 값과 인덱스번호를 추가한다

for i in result: print(i, end = ' ') # 결과 출력

---

실행 화면

---

채점 결과