(시간 초과) BOJ 1342 관련하여 질문이 있습니다

💡 질문 작성 가이드

보다 빠르고 정확한 답변을 위해, 아래 사항을 참고해 질문을 작성해주세요.

1. 간단한 내용은 ChatGPT로 먼저 확인해보세요.

기본 개념이나 용어 설명은 ChatGPT를 활용하는 것이 더 빠르고 효율적일 수 있습니다.

2. 질문하실 때, 아래 내용을 함께 적어주시면 좋아요.

어느 파트인지
섹션 3 - 브루트 포스 알고리즘[문제풀이]: BOJ 1342
내가 이해한 내용
재귀 + 백트래킹을 이용해서 푸는 방법(방법2) 중 선생님께서 작성하신 dict과 set 객체를 이용한 것이 아닌
collections.Counter를 이용하여 코드를 작성했더니 시간초과가 뜹니다.

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())

choose = []
ans = 0

sol(0)
print(ans)

궁금한 점
dict과 set을 이용해서 for문으로 직접 주입하는 방식과 Counter 컬렉션을 이용해서 사용하는 방식에 어떤 차이점 때문에 시간초과가 나는지 궁금합니다

(참고로 python3로는 시간초과가 나지만, pypy3로는 통과가 됐습니다. 이 부분도 왜 그런지 궁금합니다.)

파이썬을 선생님 강의로 입문을 해서 그런지 파이썬 기초에 대해 지식이 많이 부족합니다.
알고리즘 본질이 아닌 파이썬에 대해 질문드려 죄송합니다

안녕하세요, 인프런 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에 비해 반복적으로 수행되는 계산에서 더 나은 성능을 보인 것이 이 문제를 해결하는 데 도움이 되었던 것으로 보입니다.

성능 최적화 방법

백트래킹과 가지치기: 이미 생성 중인 문자열에서 이전 단계와 동일한 문자로 시작하지 않도록 가지치기를 더욱 철저히 하여 불필요한 탐색을 줄입니다.
데이터 구조 최적화: 코드를 더 효율적으로 수정하기 위해 중복 없는 문자열 집합을 만드는 방식, 즉 dict와 set을 사용한 방식이 Counter 대비 빠를 수 있습니다. Counter는 내부적으로 추가적인 연산을 포함할 수 있으므로, 간단한 dict를 사용하는 것이 더 효율적일 수 있습니다.
스택 메모리 최적화: 재귀 호출의 수준을 최적화하는 방법도 고려할 수 있습니다. 만약 더 깊은 단계의 호출이 문제가 된다면, 각 호출의 실행 시간을 줄이는 것도 방법이 될 수 있습니다.

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

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

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

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

💡 질문 작성 가이드

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

1. Counter 사용의 문제점

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

성능 최적화 방법

1. `Counter` 사용의 문제점