[백준] 17299번 오등큰수 - 파이썬(Python)

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

17299번: 오등큰수

 

문제

 

21.04.14 접근법

 

21.04.14 코드

n=int(input())
arr=list(map(int,input().split()))
cnt=dict()

for i in arr:
    try:
        cnt[i]+=1
    except:
        cnt[i]=1

stack=[0]
i=1
ans=[-1]*n

while stack and i<n:
    while stack and cnt[arr[stack[-1]]]<cnt[arr[i]]:
        ans[stack[-1]]=arr[i]
        stack.pop()
    stack.append(i)
    i+=1

for i in ans:
    print(i,end=' ')

 

21.07.28 접근법

 

 

[주요 변수]

arr (list) : 입력받은 수열

cnt (dictionary) : 수열이 등장한 횟수 카운트

arr_cnt (list) : 카운트된 숫자들 각 수열에 맞게 위치

ans (list) : arr_cnt의 오큰수를 찾아 해당 위치의 arr 저장

 

[과정]

1. 수열이 등장한 횟수 카운트해서 cnt에 dictionary로 저장

2. cnt에 있는 값들을 arr과 같은 위치로 하여 arr_cnt에 저장

3. arr_cnt를 앞에서부터 보며 현재의 해당 값과 arr_cnt에서 stk의 마지막 인덱스 값을 비교

4. arr_cnt의 현재 값이 더 크면 stk에서 pop하여 해당 인덱스의 arr값을 ans에서 해당 인덱스에 저장하고 이를 반복

5. 만약 arr_cnt의 현재 값이 더 작으면 stk에 해당 인덱스 append

21.07.28 코드

N=int(input())
arr=list(map(int,input().split()))
cnt={i:0 for i in arr}

for i in arr:
    cnt[i]+=1

arr_cnt=[0 for i in arr]

for i in range(N):
    arr_cnt[i]=cnt[arr[i]]


stk=[]
ans=[-1 for i in arr]

for i in range(N):
    while stk and arr_cnt[stk[-1]]<arr_cnt[i]:
        ans[stk.pop()]=arr[i]

    stk.append(i)


for i in ans:
    print(i, end=' ')