[python] 백준 17299번

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

문제

---

소스코드

1. 1차

import sys
from collections import deque

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

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

count_array = {}
stack = deque()
result = [-1] * n

for i in list(set(array)):
	count_array[i] = array.count(i)

for i in range(n):
    while stack and (count_array[array[stack[-1]]] < count_array[array[i]]):
        result[stack.pop()] = array[i]
    stack.append(i)

print(*result)

• 원소의 등장횟수를 세고 count의 중복을 없애기 위해 set()을 사용
• 결과 : 시간초과

2. 2차

import sys
from collections import deque

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

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

count_array = {}
stack = deque()
result = [-1] * n

for i in array:
    count_array[i] = array.count(i)

for i in range(n):
    while stack and (count_array[array[stack[-1]]] < count_array[array[i]]):
        result[stack.pop()] = array[i]
    stack.append(i)

print(*result)

• set()을 사용하지 않고 원소 i의 중복을 허용하여 등장횟수를 저장
• 결과 : 시간초과

3. 3차

import sys
from collections import deque, Counter

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

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

count_array = Counter(array)
stack = deque()
result = [-1] * n

for i in range(n):
    while stack and (count_array[array[stack[-1]]] < count_array[array[i]]):
        result[stack.pop()] = array[i]
    stack.append(i)

print(*result)

• collections의 Counter를 사용하여 해결

---

풀이

1차 시도 이후 set() 때문에 시간복잡도가 커서 시간초과라고 생각하고 set()을 사용하지 않고 2차 시도에서 사용하지 않았지만 2차 시도에서도 시간초과라는 결과를 보고 다른 방법을 찾기로 결심했다.

시간초과가 일어난 이유는 count였다.
count의 시간복잡도는 O(n)이고 이를 for문을 통한 반복으로 O(n2)이 된다는 것을 알았다.
이를 해결하기 위해 collections의 Counter를 사용하기로 했다.
Counter는 dictionary에서 원소에 접근할 때 O(1)의 시간복잡도를 가지게 되어 시간복잡도가 이전보다 작아 위 문제를 해결했다.