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

문제

 

https://www.acmicpc.net/problem/1342

1342번: 행운의 문자열

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

입력

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

출력

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

 

 

---

풀이

이게 정말 완전탐색이 맞을까..?

코드 짜면서도 다른 획기적인 방법이 있는 것이 아닐까..? 하는 의구심이 들어서 의욕이 떨어졌던 문제였다..

 

순서가 중요하기때문에 완전탐색으로 풀어야 할 것 같은데, 완탐하면 시간초과뜰까봐 고민이 많았다.

그래도 완탐밖에 생각이 안나서 구현해봤다.

 

입력받은 문자열을 개수별로 나눠 딕셔너리에 저장한다. ex) {a:4, b:3 ... }

그다음 마지막 문자와 딕셔너리에 숫자를 비교하여 dfs를 진행하고 딕셔너리값에서 1을 빼줬다.

딕셔너리는 call by reference여서 deepcopy를 해줬다.

 

결과는 메모리초과!

import sys
import copy
from collections import defaultdict
sys.setrecursionlimit(1000000000)

str = input()

dic = defaultdict(int)
for s in str:
    dic[s] += 1

dic = dict(dic)
answer = 0
def dfs(last, dic):
    global answer
    ndic = copy.deepcopy(dic)
    islast = True

    for d in ndic.keys():
        if ndic[d] > 0:
            islast = False
            if last != d:
                ndic[d] -= 1
                dfs(d, ndic)
                ndic[d] += 1
    if islast:
        answer += 1
    return

for d in dic:
    ndic = copy.deepcopy(dic)
    ndic[d] -= 1
    dfs(d, ndic)

print(answer)

 

다른 분 코드를 봤는데 dfs이기때문에 deepcopy를 해서 넘겨줄 필요 없이

dfs함수를 호출한 다음에 빼준 값을 원상복구 시키면 됐었다.

from collections import defaultdict
str = input()

dic = defaultdict(int)
for s in str:
    dic[s] += 1

dic = dict(dic)
def dfs(last, depth):
    if depth == len(str):
        return 1
    answer = 0
    for d in dic.keys():
        if dic[d] > 0 and last != d:
            dic[d] -= 1
            answer += dfs(d, depth+1)
            dic[d] += 1
    return answer

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