[알고리즘][백준] 17299번 오등큰수 - 파이썬(python) 풀이

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

17299번: 오등큰수

---

직접 풀어본 코드

import sys

n = int(sys.stdin.readline().rstrip())

stack = list(map(int, input().split()))

count = []

result = []

for i in range(len(stack)):

    count.append(stack.count(stack[i]))

for j in range(len(stack)):

    if stack.count[stack[j]] == max(count):

        result.append(-1)

    elif j == len(stack)-1:

        result.append(-1)

    else:

        for k in count[j+1:]:

            if count[j] < k:

                result.append(stack[count.index(k)])

                break

print(result)

시간초과가 떴다.... (오열😂

 

사실 이와 유사한 17298번 오큰수를 안풀고 바로 도전했는데 바로 백스텝해서 풀고왔다.....

 

그렇게 다시 풀어보니

import sys

n = int(sys.stdin.readline().rstrip())

number = list(map(int, input().split()))

stack = []

result = [-1] * n

for i in range(n):

    while stack and number.count(number[i]) > number.count(number[stack[-1]]):

        result[stack.pop()] = number[i]

    stack.append(i)

print(*result)

또 시간초과🤪 왜?!

 

number.count() 함수는 리스트에서 특정 원소의 개수를 세는 함수입니다. 이 함수는 리스트를 순회하면서 원소를 하나씩 비교하여 개수를 세기 때문에, 시간 복잡도가 O(n)입니다. 따라서, 리스트의 크기가 커질수록 count() 함수를 반복적으로 호출하면 메모리와 시간을 많이 소비할 수 있습니다.

찾아보니 위와 같은 이유인 것 같다.

 

그렇게 count한 것을 따로 저장하려하니 대부분의 사람들이 collections모듈의 Counter를 사용하는 것을 발견..!

(Counter 클래스는 원소의 개수를 딕셔너리 형태로 저장한다고 한다.)

from collections import Counter

n = int(sys.stdin.readline().rstrip())

number = list(map(int, input().split()))

stack = []

result = [-1] * n

count = Counter(number)

for i in range(n):

    while stack and count[number[i]] > count[number[stack[-1]]]:

        result[stack.pop()] = number[i]

    stack.append(i)

print(*result)

 

3트만에 성공