[baekjoon] 백준 1342번(파이썬): 행운의 문자열

문제

1342번: 행운의 문자열

알고리즘

- 백트래킹을 통해 문제를 수행한다.

- Counter 함수를 통해 문자열 안에 문자의 개수를 딕셔너리형으로 변환시킨다.

- 반복문을 통해 단어를 확인한다.

- 현재 단어와 이전 단어가 같거나 현재 단어의 개수가 0일 경우 다음 단어를 확인한다.

- 위 2가지 경우가 아니라면 현재 단어의 개수를 감소시키고 재귀 함수를 돌린다.

- 재귀 함수를 빠져나오게 되면 현재 단어의 개수를 다시 증가시킨다.(백 트래킹)

- 이때, 문자열의 길이와 현재 비교하고 있는 문자의 자릿수가 같으면 행운의 문자열이다.

- 반복문을 통해 모든 문자를 확인했다면 행운의 문자열의 개수를 리턴하여 출력한다.

코드

import sys
from collections import Counter


def backTracking(pre, l):
    answer = 0

    # 행운의 문자열이므로 1를 리턴
    if l == len(s):
        return 1

    # 반복문을 통해 단어를 확인
    for k in cnt.keys():
        # 현재 단어가 이전 단어일 경우와 현재 단어의 개수가 0일 경우 다음 단어를 확인한다.
        if k == pre or cnt[k] == 0:
            continue

        cnt[k] -= 1 # 현재 단어의 개수를 감소
        answer += backTracking(k, l + 1) # 백트래킹 후 리턴 받은 수를 answer에 더한다.
        cnt[k] += 1 # 현재 단어의 개수를 증가

    # answer 리턴
    return answer


s = list(map(str, sys.stdin.readline().strip()))
cnt = Counter(s) # 문자의 개수를 딕셔너리로 변환
print(backTracking('', 0))

github

GitHub - junjange/CodingTest: 내가 푼 코딩 테스트 문제와 해결법