[백준 1342번] 파이썬 - 행운의 문자열

백준 1342 - 행운의 문자열

시간 제한 2초, 메모리 제한 256MB

# 조건

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

입력

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

출력

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

# 접근 방법

• itertools의 Counter함수와 백트래킹을 이용해서 풀어준다.
• 우선 입력받은 문자열을 Counter 함수로 통해 각 알파벳마다 몇 개씩 존재하는지 딕셔너리로 만들어준다.
• 이후 백트래킹 함수를 돌리면서 현재 탐색중인 단어가
  • 직전에 배치한 단어가 아니고
  • Counter가 0이 아니라면 재귀로 현재 단어와 선택한 단어의 수 + 1을 함수의 인자로 재귀를 돌려준다.
• 현재 단어의 선택이 끝난다면 개수를 다시 +1을 해주어야 한다는 점이 중요하다.

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)