[baekjoon] 백준 17299번(파이썬): 오등큰수

문제

17299번: 오등큰수

알고리즘

- collection 모듈인 Counter 클래스를 사용

- 인덱스를 통해 오등큰수를 확인

위 문제를 풀기 전에 다음 문제를 먼저 풀면 이해하기 쉬울 것 같다.

[baekjoon] 백준 17298번(파이썬): 오큰수

코드

import sys
from collections import Counter # collections 모듈에 Counter 클래스 사용

n = int(sys.stdin.readline())
a = list(map(int, sys.stdin.readline().split()))
counter = Counter(a) # Counter 클래스를 통해 a 리스트 안에 담긴 등장 횟수를 확인
stack = [0]

res = [-1] * n

for i in range(1, n):
    # 인덱스를 통해 오등큰수가 있는지 확인
    while stack and counter[a[stack[-1]]] < counter[a[i]]:
        # 오등큰수이면 비교한 값을 팝하고 오등큰수를 입력받는다.
        # 위 과정을 오큰수 리스트가 사라지거나 오등큰수가 아닐 때까지 한다.
        res[stack.pop()] = a[i]

    # 오등큰수를 비교할 인덱스를 추가한다.
    stack.append(i)

print(*res)

 

실패한 코드(시간 초과)

import sys

n = int(sys.stdin.readline())
a = list(map(int, sys.stdin.readline().split()))

stack = [0]
res = [-1] * n
cnt = []
for i in range(1, n):

    while stack and a.count(a[stack[-1]]) < a.count(a[i]):
        res[stack.pop()] = a[i]

    stack.append(i)
print(*res)

count()의 시간 복잡도는 O(N)이다. 

위 코드에서 for문을 통해 count()를 n번 사용했기 때문에 총 시간 복잡도는 O(N^2)이 되면서 코드가 터지게 된다.

위 코드처럼 count()를 많이 사용하는 경우에는 collection 모듈인 Counter 클래스를 사용해야 유리하다.

Counter 클래스는 딕셔너리 형태로 Key 값으로 요소의 이름, Value 값으로 요소들의 개수를 출력해준다.

Counter 클래스를 이용해 딕셔너리 형태로 바꾸는데 O(N)의 시간 복잡도가 걸리고 딕셔너리에서 요소를 접근할 때의 시간 복잡도는 O(1)이 걸리게 된다.

따라서 count()를 여러 번 사용하는 경우에는 collection 모듈인 Counter 클래스를 사용하는 것이 더 유리할 것 같다.

github

GitHub - junjange/CodingTest: 내가 푼 코딩 테스트 문제와 해결법