인프런 커뮤니티 질문&답변

안녕하세요, Sung Hyun Hong님!

(질문 등록 알람이 안 와서 좀 늦게 답변드렸네요.. 😅)

Counter 컬렉션을 이용하면 시간 초과가 나는 이유

결론부터 말씀드리면 Counter 객체에서 원소를 조회하는 연산이 Dict 객체에서 원소를 조회하는 연산보다 약간 더(1-3배 정도) 느려서 생기는 현상입니다.

Counter 객체에서 원소를 조회하는 연산 또한 내부적으로는 Dict 객체로 구현되어 있지만, 잡다한 연산들(메서드를 호출하는 연산, 키를 검사하는 연산)이 추가적으로 들어가서 살짝 더 느립니다. 그리고 이러한 이유 때문에 Dict로 키를 조회하는 것보다 살짝 더 느린 것이죠.

보통 문제에서는 이러한 차이가 크게 작용하지 않지만, 이번 문제에서는 연산 횟수가 크다 보니 시간 초과 여부를 걸정할 정도로 작용한 것입니다.

정리하자면, Counter 객체에서 원소를 조회하는 연산 또한 내부적으로 Dict를 사용하지만 여러 연산이 더해져 Dict로 원소를 조회하는 것보다 살짝 더 느려 시간 초과가 나는 것입니다.

아래와 같이 Counter 객체를 Dict로 바꿔서 조회하는 방식으로만 바꿔도 통과하는 걸 알 수 있습니다.

from itertools import permutations
from collections import Counter

s = input()

def sol(lev):
	global s, counter, choose, ans

	# base case
	if lev == len(s):
		ans += 1
		return

	# recursive case
	for k in chars:
		if counter[k] == 0:
			continue

		if (not choose) or (choose[-1] != k):
			counter[k] -= 1
			choose.append(k)

			sol(lev + 1)

			choose.pop()
			counter[k] += 1

counter = Counter(s)
chars = tuple(counter.keys())
counter = dict(counter) # 추가된 부분

choose = []
ans = 0

sol(0)
print(ans)

Python3와 PyPy3 차이점

Python3와 PyPy3 모두 파이썬 컴파일러이며, 컴파일하는 방식에 차이가 있습니다. PyPy3는 Python3에 비해 메모리를 더 쓰는 대신에 효율적으로 컴파일하는 특징이 있어 똑같은 코드라도 PyPy3에서 더 빠르게 돌아가는 경향이 있습니다. 하지만 Python3보다 메모리를 더 사용하는 방식으로 작동하니 메모리 제한이 작은 문제에서는 주의해야 합니다. 이 부분 관련해서는 섹션2의 16. 🎁 백준에 파이썬 코드를 제출할 때 주의할 점를 참고하시면 도움이 될 것 같습니다.

질문에 대해 만족스러운 답변이 되었기를 바랍니다!

추가로 궁금하신 점이나 더 자세한 설명이 필요하시다면 언제든지 말씀해 주세요. 😄

안녕하세요, 인프런 AI 인턴입니다. tmdwhd319님.

질문 주신 BOJ 1342번 문제에 대한 해결 방법과 시간을 초과하는 이유에 대한 답변 드립니다. 이 문제는 문자열을 순회하면서 가능한 모든 “행운의 문자열”을 생성하며, 연속된 문자가 없는 문자열을 구하는 문제입니다.

시간 초과의 원인과 해결 방안

1. Counter 사용의 문제점

Counter 객체는 주어진 문자열에서 각 문자의 빈도를 저장하고, 각 문자의 개수에 접근하는 데에 O(1)의 시간 복잡도를 제공합니다. 하지만 문제는 for k in chars: 반복문에서 발생할 수 있습니다. 순회하는 문자의 수가 많을수록, 각 문자에 대해 여러 조건을 검사하게 되어 시간이 오래 걸릴 가능성이 있습니다. 특히, counter[k]의 모든 키를 순회해야 하는 경우, 각 단계에서 초래하는 비용이 커질 수 있습니다.

2. PyPy3와 Python3의 시간 초과 차이

PyPy는 JIT(Just-In-Time) 컴파일러를 사용하여 파이썬 코드를 보다 최적화된 기계어로 변환하고, 반복적인 연산에 강점을 보여주는 런타임을 갖추어 Python보다 빠른 결과를 제공할 수 있습니다. PyPy가 Python에 비해 반복적으로 수행되는 계산에서 더 나은 성능을 보인 것이 이 문제를 해결하는 데 도움이 되었던 것으로 보입니다.

성능 최적화 방법

1. 백트래킹과 가지치기: 이미 생성 중인 문자열에서 이전 단계와 동일한 문자로 시작하지 않도록 가지치기를 더욱 철저히 하여 불필요한 탐색을 줄입니다.

2. 데이터 구조 최적화: 코드를 더 효율적으로 수정하기 위해 중복 없는 문자열 집합을 만드는 방식, 즉 dict와 set을 사용한 방식이 Counter 대비 빠를 수 있습니다. Counter는 내부적으로 추가적인 연산을 포함할 수 있으므로, 간단한 dict를 사용하는 것이 더 효율적일 수 있습니다.

3. 스택 메모리 최적화: 재귀 호출의 수준을 최적화하는 방법도 고려할 수 있습니다. 만약 더 깊은 단계의 호출이 문제가 된다면, 각 호출의 실행 시간을 줄이는 것도 방법이 될 수 있습니다.

비슷한 문제에 대한 해결책을 찾고 싶다면, 다음 링크를 참고해 보실 수 있습니다:
- 저.. 시간복잡도 관련 질문입니다.(로직 거의 비슷한 거 같은데, 시간초과가 나서요)
- 브루토 포스 백준 1342 질문

이 링크들은 유사한 문제에 대한 해결책과 조언을 제공하고 있습니다.

저는 질문자님의 이해를 돕고자 지식공유자님의 기존 답변을 참고하여 유사한 답변 링크를 추천해드리고 있습니다. 현재 베타 기능으로 답변이 만족스럽지 않을 수 있는 점 양해 부탁드립니다. 🙏 추가적으로 궁금한 점이 있으시면, 이어서 질문해 주세요. 곧 지식공유자께서 답변해 주실 것입니다.