5️⃣ 백준 - 17299 오등큰수

우리팀~

저녁 때는 다른 팀이랑도 밥 먹었다!

블레어 언니가 하는 운동 동아리도 가입

---

# 17299

오등큰수

🥇3

 

웰논 오큰수를 생각나게 하는 네이밍..

 

오큰수는 어떻게 풀었냐면..스택에 쇽샥쇽샥

 

 

 

 Ai의 오등큰수: 오른쪽에 있으면서 수열 A에서 등장한 횟수가 F(Ai)보다 큰 수 중에서 가장 왼쪽에 있는 수

등장한 횟수로 바뀌었군..

 

우선 그럼 각 수에 대해 등장 횟수를 카운트한다그다음에 스택 슥삭슥삭

import sys
N = int(sys.stdin.readline())
A = list(map(int, sys.stdin.readline().split()))
A_list = []
for a in A:
    A_list.append((a, A.count(a))) 

my_stack =[]
result = []
A_list.reverse()
for a in A_list:
    while(my_stack and my_stack[-1][1] <= a[1]):
        my_stack.pop()

    if not my_stack:
        result.append(-1)
    else:
        result.append(my_stack[-1][0])
    my_stack.append(a)

result.reverse()
print(*result)

시간 초과!!!!!!!!!!!!!!!!!!!!

 

흠.,

for a in A:
    A_list.append((a, A.count(a)))

이게 O(N**2)군..

 

time_reduce = [0 for i in range(1000_001)]
for a in A: time_reduce[a] += 1
for a in A: A_list.append((a, time_reduce[a]))

ㅋㅋㅋㅋㅋㅋ이게 맞나

맞았으니까 됐다

---

엄청느림.,..