오등큰수

백준 17299

오등큰수 구하기.

• 크기가 N인 수열 A = A1, A2, ..., AN이 있다.
• Ai가 수열 A에서 등장한 횟수를 F(Ai)라고 했을 때, Ai의 오등큰수는 오른쪽에 있으면서 수열 A에서 등장한 횟수가 F(Ai)보다 큰 수 중에서 가장 왼쪽에 있는 수를 의미한다.
• 그러한 수가 없는 경우에 오등큰수는 -1이다.
• 첫째 줄에 수열 A의 크기 N (1 ≤ N ≤ 1,000,000)이 주어진다.
• 둘째에 수열 A의 원소 A1, A2, ..., AN (1 ≤ Ai ≤ 1,000,000)이 주어진다.

입출력

입력	출력
7 1 1 2 3 4 2 1	-1 -1 1 2 2 1 -1

---

접근 방식

: 각 원소의 등장횟수를 구하고 (등장횟수, 원소)를 새로운 배열에 저장한다. 새로운 배열에 대하여 오등큰수를 구해야 할 혹은 오등큰수를 구하지 못한 수를 스택에 (등장횟수, 원소, 인덱스)로 저장한다. 배열의 i번째 원소와 스택의 top원소를 비교하여 i번째 원소가 클 동안 pop하고 pop한 원소의 인덱스에 해당하는 배열을 i번째 원소로 업데이트한다.

시도1. count함수 사용 => 시간초과 발생.
시도2. 등장 횟수를 세어서 딕셔너리에 저장 => 성공

코드

n = int(input())
arr = list(map(int, input().split()))
result = [-1]*len(arr)

d = {} # 등장 횟수를 기록할 딕셔너리
for a in arr:
    if a in d:
        d[a] += 1
    else:
        d[a] = 1

num = []
for a in arr:
    num.append((d[a], a)) # (등장횟수, 원소)를 리스트에 저장

s = []
for i in range(len(num)):
    while s and s[-1][0] < num[i][0]:
        counti, ele, idx = s.pop()
        result[idx] = num[i][1]
    s.append((num[i][0], num[i][1], i))
print(*result)