[백준 1342] 행운의 문자열

문제

민식이와 준영이는 자기 방에서 문자열을 공부하고 있다. 민식이가 말하길 인접해 있는 모든 문자가 같지 않은 문자열을 행운의 문자열이라고 한다고 한다. 준영이는 문자열 S를 분석하기 시작했다. 준영이는 문자열 S에 나오는 문자를 재배치하면 서로 다른 행운의 문자열이 몇 개 나오는지 궁금해졌다. 만약 원래 문자열 S도 행운의 문자열이라면 그것도 개수에 포함한다.

 

입력

첫째 줄에 문자열 S가 주어진다. S의 길이는 최대 10이고, 알파벳 소문자로만 이루어져 있다.

 

출력

첫째 줄에 위치를 재배치해서 얻은 서로 다른 행운의 문자열의 개수를 출력한다.

---

접근

이전에 선택한 문자가 아닌 문자를 선택해서 문자열을 완성한다.

문자열이 완성되었다는 것은 행운의 문자열이 되었다는 의미이기 때문에 최종해를 증가시킨다.

 

구현

- 입력받은 문자열에서 각 문자의 횟수를 counter라는 딕셔너리에 저장한다.

counter = dict()
for s in S:
    if s in counter:
        counter[s] += 1
    else:
        counter[s] = 1

- pre_word는 이전 단계에서 선택한 문자가 담겨져있다.

- counter의 key값과 pre_word를 비교해서 다르고 해당 문자의 value가 0이 아닐 때 다음 단계를 위한 재귀호출을 진행한다.

- 이때 해당 key의 value를 -1하고 재귀호출이 끝나고 돌아왔을 때 다시 +1한다.

- 선택한 문자를 의미하는 picked가 처음에 입력받은 문자열의 길이와 같을 때 1을 반환한다.

def dfs(pre_word, picked):

    if picked == len(S):
        return 1
    answer = 0
    for key in counter.keys():
        if pre_word == key:
            continue
        if counter[key] == 0:
            continue
        counter[key] -= 1
        answer += dfs(key, picked+1)
        counter[key] += 1
    return answer

---

전체 코드

import sys
input = sys.stdin.readline

def dfs(pre_word, picked):

    if picked == len(S):
        return 1
    answer = 0
    for key in counter.keys():
        if pre_word == key:
            continue
        if counter[key] == 0:
            continue
        counter[key] -= 1
        answer += dfs(key, picked+1)
        counter[key] += 1
    return answer

S = list(input().strip())
counter = dict()
for s in S:
    if s in counter:
        counter[s] += 1
    else:
        counter[s] = 1

answer = dfs('', 0)
print(answer)