캬캬캬 오늘은 끝까지 정답을 보지 않고 풀어냈다 !!!! 자그마치 4번의 시간 초과 끝에 '맞았습니다'를 얻어냈다. 아주 뿌듯해 ~~!!~!

17299: 오등큰수

1. 첫 번째 풀이: 실패

사실 이 풀이는 실패할 걸 99% 예상하고 일단 적기라도 해보자... 라는 마음에서 썼다. 다시 한 번 깨달았다. count 절대 NEVER 쓰지 말기.

import sys

N = int(sys.stdin.readline())
A = list(map(int, sys.stdin.readline().strip().split()))
FA = []
answer = [-1]*len(A)
stack = []
cnt = 0

# FA 완성
for i in A:
    FA.append(A.count(i))


# 오큰수 process at FA
for index, current in enumerate(FA):
    while stack and current > FA[stack[-1]]:
        last = stack.pop()
        answer[last] = A[index]
    stack.append(index)

for i in answer:
    print(i, end=" ")

다시 한 번 깨달았다. count 절대 NEVER 쓰지 말기.

2. 두 번째 풀이: 실패

import sys

N = int(sys.stdin.readline())
A = list(map(int, sys.stdin.readline().strip().split()))
FA = []
answer = [-1]*len(A)
stack = []
cnt = 0

# FA 완성
for i in A:
    for j in A:
        if i == j:
            cnt += 1
    FA.append(cnt)
    cnt = 0
print(FA)


# 오큰수 process at FA
for index, current in enumerate(FA):
    while stack and current > FA[stack[-1]]:
        last = stack.pop()
        answer[last] = A[index]
    stack.append(index)

for i in answer:
    print(i, end=" ")

count 안 쓰면 난 뭐 써...? 뭐로 세...? 중첩 반복문 말고 더 방법이 있습니까 콤퓨타...? 라는 마음으로 썼다. 물론 당연히 시간 복잡도가 O(n)에서 O(n square)로 늘어났으니 당연히 실패 ~~~

count 시간복잡도 찾아보다가 Counter이라는 클래스를 알게 되었다!

3. 세 번째 풀이: 실패

import sys
from collections import Counter

N = int(sys.stdin.readline())
A = list(map(int, sys.stdin.readline().strip().split()))
FA = []
answer = [-1]*len(A)
stack = []
cnt = 0

# FA 완성
for i in A:
    FA.append(Counter(A)[i])

# 오큰수 process at FA
for index, current in enumerate(FA):
    while stack and current > FA[stack[-1]]:
        last = stack.pop()
        answer[last] = A[index]
    stack.append(index)

for i in answer:
    print(i, end=" ")

자 여기서 틀린 이유를 찾으시오.

정답은 for 문을 돌 때마다 Counter를 돌아야 하기 때문에 아마도 시간복잡도가 O(n square)가 될 것이기 때문이다(?) 정확한지는 모르겠지만, 확실한 건 for문 돌 때마다 계속 Counter 호출해야 해서 매우 비효율적이라는 사실! 조금 더 코드를 간결하게 짜고 싶어서 저렇게 작성했는데, 오히려 역효과를 불러일으켰다.

4. 네 번째 풀이: 성공

import sys
from collections import Counter

N = int(sys.stdin.readline())
A = list(map(int, sys.stdin.readline().strip().split()))
FA = []
answer = [-1]*len(A)
stack = []
cnt = 0

# FA 완성
FA_count = Counter(A)
for i in A:
    FA.append(FA_count[i])

# 오큰수 process at FA
for index, current in enumerate(FA):
    while stack and current > FA[stack[-1]]:
        last = stack.pop()
        answer[last] = A[index]
    stack.append(index)

for i in answer:
    print(i, end=" ")

Counter 반환값을 변수에 할당하니까 아주 잘 작동했다! 제출해놓고 percentage가 너무너무 천천히 올라가길래 정말 심장 쫄면서 쳐다봤다. 하지만 다행히 ~

영광의 '맞았습니다.'
메모리? 그런 건 모르겠고... 일단 통과했다에 의의를 두기 ^^
오늘 기억해야 할 부분은,

1. count를 쓰지 않으면 정말 죽을 것 같다가 아니라면 쓰지 말자.
2. Counter(Collection)는 딕셔너리로 반환한다.
3. 코드의 간결성도 중요하지만 시간 복잡도를 먼저 고려하자! (변수 선언의 중요성)

5. 다른 풀이

대부분의 다른 풀이가 나처럼 따로 FA(등장한 횟수)를 따로 정의하지 않고 바로 오큰수 과정으로 넘어갔다. 이 방법도,,, 신기하군,,, 굳이 메모리를 더 차지할 필요가 없다는 장점이 있는 것 같다.
(출처: https://joosjuliet.github.io/17299/)

import sys
input = sys.stdin.readline

from collections import Counter

n = int(input())
aa = list(map(int,input().split()))
ff = Counter(aa)
stack = []
ngf = [-1] * n

for i in range(n):
    while stack and ff[aa[stack[-1]]] < ff[aa[i]]:
        ngf[stack.pop()] = aa[i]
    stack.append(i)

print(*ngf)

제출해서 시간이랑 메모리를 확인해보면,

이와 같다. 오히려 내 풀이가 시간이 더 적네 ㅋㅎㅋㅋㅎㅎㅋ
집중해야할 부분은 최대한 메모리랑 시간을 줄이기...!

오늘도 신기한 알고리즘의 세계 끝!