[BOJ] 1342. 행운의 문자열(Python) / DFS

www.acmicpc.net/problem/1342

1342번: 행운의 문자열

내가 짠 코드는 15분만에 간단한 DFS로 순열(Permutation)을 구현했지만, 중복 고려하지 않고 문자열 그대로 완전탐색해버리니, 3300ms로 겨우 통과했다.. 부끄러워서 차마 내 코드는 올릴 수가 없다. 

이번에 소개할 코드는 내가 짠 건 아니고, "뚱이"라는 나의 짝꿍이 짰다. 토실토실 아주 귀여운 친구다.

• 문자열의 각 알파벳별 카운트로 계산한다. 아스키 코드 변환(ord()함수 사용)으로 a~z까지 0~25에 해당하는 문자의 자리에 카운트를 올려준다.(cntMap)
• 다음 dfs 함수의 for문에서 각 문자들(중복 제거된 charSet)을 한 번씩 순차적으로 넣으며 해당 자리에 들어올 문자의 카운트가 남아있는지 확인하여 넣을 수 없다면 더이상 시도하지 않아 중복을 제거할 수 있다. 
• for문 내 조건문에서 문자열의 길이가 0보다 크고 문자열의 마지막 문자가 현 문자와 같다면 더이상 진행하지 않는다.(멀리 안 나간다!)
• depth == N(주어진 문자열의 길이)이 될 때 출력한다.

 

 

파이썬 코드는 다음과 같다.

---

from sys import stdin
input = stdin.readline

def dfs(depth, string):
    global N, ret, charSet, cntMap

    if depth == N:
        # print(string)
        ret += 1
        return

    for char in charSet:
        idx = ord(char) - ord('a')
        if cntMap[idx] == 0:
            continue

        if string and string[-1] == char:
            continue

        cntMap[idx] -= 1
        dfs(depth + 1, string + char)
        cntMap[idx] += 1


raw = input().strip()
cntMap = [0] * 26
N = len(raw)
ret = 0
charSet = set()

for char in raw:
    idx = ord(char) - ord('a')
    cntMap[idx] = cntMap[idx] + 1
    charSet.add(char)
# print(charSet, cntMap, cntSum)

dfs(0, '')
print(ret)

---

• 시간 : 1236ms / 메모리 : 126804KB
• 고찰 : 깔끔하게 잘 짠 코드같다. 이와 같은 문제가 나오면 딕셔너리 or 위와 같이 카운트리스트를 구해놓고 dfs 내에서 중복 제거한 문자만 돌리면 보다 효율적일 것이다. 도와줘서 고맙다 뚱아!