[Baekjoon]백준 17299 오등큰수(골드 3) - Python

문제설명

문제를 살펴보면 이전 문제와 거의 유사하지만, 등장횟수에 따라 결정된다는 점에서 차이가 있다

간단하게 이전 동작 과정은 설명하였기 때문에 이 글에서는 과정을 직접 예시로 서술하도록 하겠다

일단, 딕셔너리를 활용하여 각 원소가 몇 번 등장하였는지 저장하고 이를 저장하는 리스트를 따로 만들어주었다

이후에는 이전 문제와 동일하게 작성하면 되는데, 해당 for문을 i의 수에 따라 예시를 보여주도록 하겠다

new 3 3 2 1 1 2 3 ( count 결과 저장 )
ngf  1 1 2 3 4 2 1  ( 입력값 )

---

▶ i = 0일 때

stack 0
result -1 -1 -1 -1 -1 -1 -1

stack에 아무것도 없던 상태였기 때문에 stack.append(i)만 실행되어 stack에 0이 저장된다

result에는 아무 변화가 없다

---

▶ i = 1일 때

stack 0 1
result -1 -1 -1 -1 -1 -1 -1

stack에 내용은 존재하지만, count의 값이 더 크지 않고 3 < 3이기 때문에 stack.append(i)만 실행된다

result에는 아무 변화가 없다

---

▶ i = 2일 때

stack 0 1 2
result -1 -1 -1 -1 -1 -1 -1

stack에 내용은 존재하지만, 3 < 2이므로 stack.append(i)만 실행된다

result에는 아무 변화가 없다

---

▶ i = 3일 때

stack 0 1 2 3
result -1 -1 -1 -1 -1 -1 -1

stack에 내용은 존재하지만, 2 < 1이므로 stack.append(i)만 실행된다

result에는 아무 변화가 없다

---

▶ i = 4일 때

stack 0 1 2 3 4
result -1 -1 -1 -1 -1 -1 -1

stack에 내용은 존재하지만, 1 < 1이므로 stack.append(i)만 실행된다

result에는 아무 변화가 없다

---

▶ i = 5일 때

stack 0 1 2 5
result -1 -1 -1  2  2 -1 -1

stack에 내용도 존재하고, 1 < 2이므로 result[4] = NGF[5]가 저장된다

또한 stack.pop()한 결과가 3인데 1 < 2이므로 result[3] = NGF[5]가 저장된다

---

▶ i = 6일 때  

stack 0 1 6
result -1 -1 1  2  2 -1 -1

stack에 내용도 존재하고 2 < 3을 만족하므로 result[2] = NGF[6]이 저장된다

그 외에는 만족시키는 조건이 없기 때문에 이대로 for문이 종료된다

---

stack에 index를 저장한다고 생각하고, pop()을 통해 더 큰 수를 찾고 이를 반복하는 과정이라고 생각하면 된다

import sys
input = sys.stdin.readline

size = int(input())
NGF = list(input().split())

count_NGF = {}
for num in NGF:  # 각 숫자의 등장 횟수 계산
    if num in count_NGF:
        count_NGF[num] += 1
    else:
        count_NGF[num] = 1

new_NGF = [count_NGF[num] for num in NGF]

stack = []
result = [-1] * size
for i in range(size):
    while stack and new_NGF[stack[-1]] < new_NGF[i]:
        result[stack.pop()] = NGF[i]
    stack.append(i)
   
print(*result)