[Baekjoon 1342] 행운의 문자열

문제

🤍Ⅰ [Baekjoon 1342 - 행운의 문자열]

문제 풀이 방법

실버문제인데 골드보다 더 어려운 것 같다.. 여전히 백트래킹과 같은 재귀문제는 어렵다ㅜㅜ 처음에는 순열 조합으로 개수를 모두 계산하는 알고리즘을 작성하였으나 예외를 전혀 생각하지 못한 풀이라는 것을 깨닫고 백트래킹을 사용하는 방법으로 처음부터 다시 풀이하였다.

1. dictionary를 이용하여 같은 알파벳의 개수를 센다.
2. 계속 앞문자와 다른 문자를 연결하여 최종 문자열의 길이와 같은 문자열을 생성하는 재귀함수를 구현한다.
   1. 매개변수에 있는 연결하고 있는 문자열의 개수와 s의 길이가 같다면 total += 1을 해준다.
   2. 아직 문자열을 더 연결해야 한다면, dictionary에 있는 문자들을 순회하면서 앞 문자와 다른 문자이면서 개수가 1개 이상 남아 있는 문자를 연결해주고 다시 재귀함수를 호출한다. 재귀함수 호출 후 연결했던 문자는 다시 되돌려준다.

풀이 코드

Python

import sys
input = sys.stdin.readline

# 바로 앞 문자와 같은지 체크
def dfs(pre_char, length):
    global total
    if length == len(s):
        total += 1
        return

    for key in dic.keys():
        if pre_char != key and dic[key] != 0:
            dic[key] -= 1
            dfs(key, length + 1)
            dic[key] += 1 # 다시 되돌려 주기

s = input().rstrip()
dic = {}
for i in s:
    if i in dic:
        dic[i] += 1
    else:
        dic[i] = 1

total = 0
dfs("", 0)
print(total)