브루토 포스 백준 1342 질문

Question

s = list(input()) n = len(s) choose = [] check = [False] * len(s) ans = [] def check_ad(s): for i in range(len(s)-1): if s[i] == s[i+1]: return False return True def make(level): if level == n and check_ad(choose): result = ''.join(choose) if result not in ans: ans.append(result) for i in range(n): if check[i]: continue choose.append(s[i]) check[i] = True make(level + 1) choose.pop() check[i] = False make(0) print(len(ans))   안녕하세요 강사님! 위 코드는 시간 초과가 나는데 순열 강의 알고리즘을 그대로 사용한 것입니다! 강사님의 순열 코드는 시간 초과가 안나는데 왜 이거는 시간초과가 날까요? 내장된 permutation이 효율적으로 구현된 것일까요?

알리 Ally · Answer

안녕하세요. Taejin Kim님! 공유해주신 코드를 보니, ans는 행운의 문자열을 담는 리스트로 어떤 문자열이 행운의 문자열이고 ans에 존재하지 않는다면 계속 추가하는 형식의 풀이인 걸로 확인이 됩니다.   element in list 의 시간 복잡도는 list 의 크기 만큼의 연산이 걸린다고 생각하시면 됩니다.   따라서 행운의 문자열의 최대 개수는 10!으로 약 360만이고, 행운의 문자열 1개를 추가할 때마다 ans에 해당 문자열의 존재 여부를 in 문법을 통해서 판단하기 때문에 최악의 경우에 1 + 2 + 3 + ... + 360만 의 연산횟수가 걸리게 됩니다. 이런 이유로 시간초과가 나게 되는 것입니다.   그러므로 좀 더 효율적으로 행운의 문자열의 개수를 세야 하며, 그러한 방법은 백트레킹을 이용한 풀이 또는 같은 것이 있는 순열을 이용한 풀이 이며, 이는 강의를 참고해 주시면 감사하겠습니다.   또 궁금하신 점 있으시면 언제든 질문 부탁드립니다. 감사합니다. :)

인프런 AI 인턴 · Answer

안녕하세요, 인프런 AI 인턴입니다. Taejin Kim님. 주신 코드는 입력 문자열에서 &lsquo;행운의 문자열&rsquo;을 만들기 위해 모든 가능한 순열을 조사하려는 방식으로 작성되어 있습니다. 주어진 알고리즘에서 문제가 되는 점은 check_ad 함수가 불필요하게 탐색의 모든 단계에서 중복을 검사하게 되며, 이는 비효율적입니다. 순열을 생성하고 난 후에 매번 choose 리스트의 연속된 문자가 같은지 체크하는 check_ad 함수 호출이 있기 때문에 전체적인 시간 복잡도가 크게 증가하게 됩니다. 파이썬 내장 모듈에서 제공하는 itertools.permutations 는 보다 효율적으로 최적화된 C언어로 구현되어 있어서, 일반적으로 큰 데이터에 대해서도 성능이 우수합니다. 또한, 내장 함수는 중복 제거나 정렬 등의 추가 작업 없이 바로 순열 생성을 최적의 방식으로 처리합니다. 이를 해결하기 위한 방법으로는 중복 검사를 미리 수행하여 불필요한 탐색을 줄이는 것입니다. 이렇게 적절한 가지치기를 한다면, 탐색하는 경우의 수를 크게 줄여 시간 초과를 방지할 수 있습니다. 예를 들어, 이미 선택한 문자가 마지막 선택한 문자와 동일하다면 그 상태에서는 추가적으로 탐색을 하지 않도록 가지치기를 할 수 있습니다. 관련된 기존 답변을 참고하고 싶다면 여기 의 답변도 확인해 보세요. 유사한 백트래킹 문제에 관한 답변과 성능 최적화를 위한 가이드라인을 제공하고 있습니다. 저는 질문자님의 이해를 돕고자 지식공유자님의 기존 답변을 참고하여 유사한 답변 링크를 추천해드리고 있습니다. 현재 베타 기능으로 답변이 만족스럽지 않을 수 있는 점 양해 부탁드립니다. 🙏 추가적으로 궁금한 점이 있으시면, 이어서 질문해 주세요. 곧 지식공유자께서 답변해 주실 것입니다.