[백준] 오등큰수

출처:: www.acmicpc.net/problem/17299

분류:: 스택

 

1. 문제 이해 및 해결과정

- 오큰수와 유사 hiruby.tistory.com/493

 

2. 풀이방법

  1. 스택

#오등큰수
#https://www.acmicpc.net/problem/17299
import sys
from collections import Counter
sys.stdin = open("input.txt","r")
n=int(input())
#O(logN) O(N) O(1)로 풀어야함
arr = list(map(int, sys.stdin.readline().split()))
cnt=Counter(arr)
arr =[[index,cnt[index]] for index in arr] #수와 횟수를 넣음
stack = []
result= [-1 for _ in range(n)]

for i in range(len(arr)): #인덱스를 이용
    while stack and arr[stack[-1]][1]<arr[i][1]: #횟수 비교
        #현재 스택의 top이 arr[i]보다 작다면
        result[stack.pop()]=arr[i][0] #stack.pop()이 인덱스, result의 인덱스에 최대값
    stack.append(i)
print(*result)

 

3. 오답원인

 

4. 알게된 점

 파이썬 개수 세는함수 다루기 

- 개수세는 함수를 배열에 넣어도 접근할 수 없다

- 접근을 위해서는 새롭게 배열을 구성해 주어야 한다.

from collections import Counter
arr = list(map(int, sys.stdin.readline().split()))
cnt=Counter(arr)
arr =[[index,cnt[index]] for index in arr] #수와 횟수를 넣음