백준 1342 행운의 문자열 Python

🐸 문제 정보

1342번: 행운의 문자열

 

🤖 알고리즘

백트래킹

 

⏱️ 풀이 시간

14.41m

 

📝 풀이

처음에 순열로 풀어야하는 문제라고 생각해서... 도대체 어떻게 풀어야하지?! 고민했는데

다시 천천히 생각해보니 그냥 Counter 써서 뒤에 뭐올지 백트래킹해도 될 것 같다고 느꼈다.

이유는 문자열 길이가 10까지밖에 안돼서...

이미 예제에 나와있는 경우가 최악의 경우였다.

 

🧑‍💻 나의 답

# pypy3

import sys
from collections import Counter
input = sys.stdin.readline

word = list(input().rstrip())
length = len(word)
letters = Counter(word)
res = set()

def bt(prev, cur):
    if len(cur) == length:
        res.add(cur)
        return
    for letter in letters:
        if (prev == letter) or (letters[letter] == 0): continue
        letters[letter] -= 1
        bt(letter, cur + letter)
        letters[letter] += 1

bt('-', '')

print(len(res))