BOJ 17299(오등큰수)풀이

solved.ac 난이도: 골드 3

www.acmicpc.net/problem/17299

17299번: 오등큰수

이문제를 그냥 2중 반복으로 풀면 시간 초과가 무조건 뜬다.

import sys
input=sys.stdin.readline
a=int(input())
l=[0]*(10000001)
t=list(map(int,input().split()))
o=0
for i in range(a):l[t[i]]+=1
for i in range(a):
    o=0
    for g in range(i+1,a):
        if l[t[g]]>l[t[i]]:print(t[g],end=" ");o+=1;break
    if o==0:print(-1,end=" ")

(부계사진)

어떻게 하면 고칠 수 있을까?

이문제는 해당 값의 개수보다 많은 개수를 가지고 있는 가장 왼쪽 값을 출력하는 것이다. 그러면 구간의 가장 큰 값과 위치를 저장해서 위치까지 반복을 해주면 된다. 이유는 만약 한 위치에 개수가 가장 큰 값이 있다면 그다음으로는 무조건 나오지 않기 때문에 반복을 그 위치에서 멈춰주면 된다.

이렇게 바꿔주고

import sys
input=sys.stdin.readline
a=int(input())
l=[0]*(10000001)
p=[0]*(a+1)
t=list(map(int,input().split()))
o=0
end=[a,0]
for i in range(a):
    l[t[i]]+=1
for i in range(a-2,-1,-1):
    o=0
    for g in range(i+1,end[0]):
        if l[t[g]]>l[t[i]]:
            if end[1]<l[t[g]]:
                end=[g+1,l[t[g]]]
            p[i]=t[g]
            o=1
            break
    if o==0:
        p[i]=-1
        end=[i+1,l[t[i]]]
for i in range(a-1):
    print(p[i],end=" ")
print(-1)

(부계사진)