백준 17299번 <오등큰수>

백준 알고리즘 17299번

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

17299번: 오등큰수

---

17299번

수열 A가 있을 때, 각 수열의 값에 대하여 자신보다 오른쪽에 있으면서 자신보다 빈도수가 많은 수 중 가장 왼쪽에 있는 수, 오등큰수를 구하여라.

 

입력으로 수열 A의 길이 N이 들어오고 그 다음 줄에 N개의 숫자가 주어진다.

 

출력으로 각 수열의 값에 대하여 오등큰수를 구해 출력하면 된다.

---

문제 해결

문제 이해가 너무 어려웠다. 

문제를 이해하고 나니 오큰수랑 똑같은 문제라는 것을 알 수 있었다. 다른 점은 오큰수는 수열의 값 자체로 하는 것이고 오등큰수는 수열의 값의 빈도수를 가지고 한다는 것이었다.

 

수열 A의 값을 (수열 A의 값, 빈도수) 로 바꾸어주었다. 그러고 나서 오큰수와 똑같이 풀었다.

• 배열의 뒤에서부터 보면서
• stack이 비어있다면 오등큰수가 없는 것이고
• 그렇지 않다면 stack의 top의 빈도수 값이 자신의 빈도수보다 클 때까지 pop을 한다.
• 배열의 값을 stack에 넣는다.

배열의 뒤에서부터 보기 때문에 바로 출력하면 안되고(거꾸로 나온다.) answer 배열에 저장해두었다가 출력하였다. 

---

코드

n = int(input())
A = list(map(int, input().split()))
cnt = {}
for i in range(n):
    cnt.setdefault(A[i], 0)
    cnt[A[i]] += 1
A = [(A[i], cnt[A[i]]) for i in range(n)]
stack = []
answer = [-1] * n
for i in range(n-1, -1, -1):
    if len(stack) != 0:
        while stack[-1][1] <= A[i][1]:
            stack.pop()
            if len(stack) == 0:
                break
        if len(stack) != 0:
            answer[i] = stack[-1][0]
    stack.append(A[i])

print(*answer) #배열의 값을 띄어쓰기로 구분해서 모두 출력

---

결과

---