백준 1342
- 민식이와 준영이는 자기 방에서 문자열을 공부하고 있다. 민식이가 말하길 인접해 있는 모든 문자가 같지 않은 문자열을 행운의 문자열이라고 한다고 한다.
- 준영이는 문자열 S를 분석하기 시작했다. 준영이는 문자열 S에 나오는 문자를 재배치하면 서로 다른 행운의 문자열이 몇 개 나오는지 궁금해졌다. 만약 원래 문자열 S도 행운의 문자열이라면 그것도 개수에 포함한다.
- 첫째 줄에 문자열 S가 주어진다. S의 길이는 최대 10이고, 알파벳 소문자로만 이루어져 있다. 첫째 줄에 위치를 재배치해서 얻은 서로 다른 행운의 문자열의 개수를 출력한다.
입출력
| 입력 | 출력 |
|---|---|
| aabbbaa | 1 |
접근 방식
: Counter를 이용해서 각 문자와 개수를 구한다. 그 이후에 인접해 있는 문자열이 같지 않도록 어떻게 하지?
알게된 점
- 백트래킹으로 이전 문자, depth를 인자로 넘긴다.
depth가 문자열의 길이와 같으면 행운의 문자열이 하나 만들어진 것이므로 1을 리턴한다.- for문을 돌려 counter의 key를 가지고
- 이전 문자와 key가 같으면 넘어간다.
- key의 개수가 0이면 넘어간다.
- key의 개수를 하나 줄이고 dfs로 key와 depth+1을 넘긴다.
- 끝까지 dfs를 수행하면 바로 이전 상황에서 dfs의 밑의 코드가 실행되면서 a, b개수를 다시 채운다.
- 베이스에 도달할때까지 수행
코드
from collections import Counter
import sys
def dfs(pre, depth):
if depth == len(s):
return 1
ans = 0
for key in counter.keys():
if pre == key:
continue
if counter[key] == 0:
continue
counter[key] -= 1
ans += dfs(key, depth+1)
counter[key] += 1
return ans
s = sys.stdin.readline().rstrip()
counter = Counter(s)
dfs('', 0)
