- Problem Link : https://www.acmicpc.net/problem/17299
문제
자신보다 오른쪽에 있으면서 등장 횟수가 더 많은 수 중에서 가장 왼쪽이 있는 수를 오등큰수라고 한다. 없는 경우에는 -1이라고 한다. 크기가 N인 수열이 A가 주어질 때 각각의 오큰수를 구해보아라.
입력
- 첫째 줄, 수열의 A의 크기 N이 주어진다.
- 둘째 줄, 수열 A가 주어진다.
출력
- N개의 오등큰수를 출력한다.
풀이
바로 직전 문제 17298번 오큰수와 동일한 방식으로 해결하나 중요한 점은 오큰수 문제의 경우 해당 숫자 자체를 크기 비교해서 pop을 해줬다면 이 문제는 등장 횟수를 비교해야하므로 등장 횟수를 따로 딕셔너리형으로 해당 숫자를 key로 해서 등장 횟수를 value로 저장해두고 비교할 때 해당 key로 가서 등장 횟수를 가져와 비교하는 그러한 방식으로 구현한다.
- 방식은 오큰수와 동일하지만 값 대신 등장 횟수를 비교하게 구현한다.
- 등장 횟수를 저장하는 딕셔너리형을 하나 추가해서 비교적 쉽게 해결할 수 있다.
0. 모든 원소를 방문하면서 해당 원소의 등장 횟수를 측정해 dict 자료형에 해당 수를 key값으로 등장 횟수를 value에 추가한다. 이 때 만약 dict에 있는 key라면 굳이 count를 해주지 않고 지나간다.
count 함수도 결국 모든 원소를 방문하면서 count 해주는 방식이기 때문에 실행 시간을 줄이기 위해서 이미 등장 횟수를 알고 있는 원소의 경우는 스킵하면서 등장 횟수를 계산한다.
오류 및 해결
원래는 count함수를 이용해 등장 횟수를 측정하고 dict에 해당 key값이 없는지 in 함수를 이용해 확인하고 없다면 추가하는 방식으로 갔는데 시간초과가 발생했다.
그래서 Collections의 Counter 클래스를 사용하니 시간초과 없이 해결됐다. 이 두 가지 모두 원소의 갯수를 세는 것은 동일하나 시간적으로 어떤 차이가 있는 것일까?
count 함수와 Counter 클래스의 차이점
count 함수는 인수가 매핑인지 여부를 확인하기 위해 매 원소별로 isinstance 호출이 포함되어 시간이 굉장히 오래 걸린다. 하지만 Counter 클래스는 유형 및 인스턴스 검사 없이, isinstance 호출 없이 개수를 셀 수 있어서 굉장히 빠르다. 이 때 Counter의 시간 복잡도는 O(n)에 가깝다.
이 문서를 참고하면 count 함수와 Counter 클래스의 속도 차이가 나는 원인에 대해 자세히 알아볼 수 있다.
Counter 클래스의 기본적인 사용법
from collections import Counter
>>> Counter(["hi", "hey", "hi", "hi", "hello", "hey"])
Counter({'hi': 3, 'hey': 2, 'hello': 1})이 때 Counter 클래스는 기본 자료구조인 딕셔너리를 확장하고 있기 때문에 딕셔너리에 제공하는 API를 그대로 다 사용할 수가 있다. 따라서 기존 딕셔너리를 사용하던 코드에 Counter 클래스만 사용해서 시간 초과를 쉽게 해결할 수 있었다.
만약 입력 데이터의 수가 많을때 횟수, 개수를 세야한다면 Counter 클래스를 활용해서 빠르게 딕셔너리 형으로 된 결과를 빠르게 얻을 수 있음을 기억해두자.
코드
import sys
from collections import deque
from collections import Counter
input = sys.stdin.readline
n = int(input())
a = list(map(int, input().split()))
q = deque()
cnt = Counter(a)
ans = []
for i in range(n - 1, -1, -1):
while q and cnt[q[-1]] <= cnt[a[i]]:
q.pop()
if not q:
ans.append(-1)
else:
ans.append(q[-1])
q.append(a[i])
ans.reverse()
print(*ans)
ans = []
