행운의 문자열 ( 1342 번 )

1342번: 행운의 문자열

---

🧠 알고리즘

백트래킹 알고리즘을 사용해
같은 문자가 연속되지 않는 문자열의 순열 개수를 구하는 문제입니다.

✔️ 동작 방식

• 함수 _BT(pre_str, now_lenth)를 재귀적으로 호출하여 경우의 수 탐색
• 다음 조건을 만족하는 문자만 사용:
  1. 현재까지 만든 문자열의 길이가 원래 문자열 길이와 같으면 정답으로 인정
  2. 문자가 아직 남아 있고, 바로 앞 문자와 다를 경우만 선택
• 선택한 문자를 사용한 후 백트래킹 호출,
  호출이 끝나면 원래 상태로 복구하여 다음 분기 탐색

---

🧾 코드

import sys
from collections import Counter

def _BT(pre_str, now_lenth):
    """ 백 트래킹
    조건 1. 길이가 기존 문자열과 같아지면 정답
    조건 2. 이전 문자열과 다를 경우 만 트래킹 진행
    """

    global answer
    if now_lenth == lenth_n:
        answer += 1
        return

    for now_str in str_dict.keys():
        if (str_dict[now_str]) and (pre_str != now_str):
            str_dict[now_str] -= 1
            _BT(now_str, now_lenth + 1)
            str_dict[now_str] += 1
    

n = sys.stdin.readline().rstrip()
lenth_n = len(n)
str_dict = Counter(n)
answer = 0
_BT('', 0)

print(answer)

---

⏱️ 시간 복잡도

• _BT()는 백트래킹 기반의 순열 생성 함수
• 최악의 경우 모든 순열 탐색: O(n!)
• 따라서,
  ▶️ 팩토리얼 시간 복잡도 (O(n!))