각 타일에 한 글자씩 문자가 적혀 있는 타일 집합이 있다고 가정해 봅시다. 이때 타일들을 조합하여 만들 수 있는 비어 있지 않은 문자 시퀀스의 개수를 구해야 합니다. 예를 들어 입력이 "AAB"라면 출력은 8이 되며, 만들 수 있는 시퀀스는 "A", "B", "AA", "AB", "BA", "AAB", "ABA", "BAA"입니다.
이 문제는 백트래킹(backtracking) 기법을 활용하면 효율적으로 해결할 수 있습니다. 전체 풀이 과정은 다음 단계와 같습니다.
- count 배열을 매개변수로 받는 dfs() 함수를 정의합니다.
- 합계(sum)를 0으로 초기화합니다.
- i를 1부터 26까지 순회합니다.
- count[i]가 0이라면 남은 검사를 생략하고 다음 반복으로 넘어갑니다.
- count[i]를 1 감소시키고 sum을 1 증가시킵니다.
- sum := sum + dfs(count)
- count[i]를 다시 1 증가시켜 원래 상태로 복원합니다(백트래킹).
- sum을 반환합니다.
- 실제 메서드(numTilePossibilities)는 다음과 같이 동작합니다.
- 크기가 26인 count 배열을 생성하고 모든 요소를 0으로 초기화합니다.
- tiles의 각 문자 i에 대해 count[i – 'A' + 1] 값을 1씩 증가시킵니다.
- dfs(count)의 결과를 반환합니다.
여기서 핵심은 각 알파벳별 등장 횟수만 관리한다는 점입니다. 같은 문자가 여러 개 포함되어 있어도 문자 개수를 기준으로 탐색하기 때문에 중복된 시퀀스가 자연스럽게 제거됩니다. 또한 재귀 호출 시마다 문자를 하나 선택하고, 해당 분기의 탐색이 끝나면 개수를 복원하는 방식으로 가능한 모든 경우의 수를 빠짐없이 확인할 수 있습니다.
다음 구현 예제를 살펴보면 더욱 쉽게 이해할 수 있습니다.
예제
class Solution(object):
def numTilePossibilities(self, tiles):
count = [0 for i in range(27)]
for i in tiles:
count[ord(i)-ord('A')+1]+=1
return self.dfs(count)
def dfs(self,count):
summ = 0
for i in range(1,27):
if count[i]==0:
continue
count[i]-=1
summ+=1
summ+=self.dfs(count)
count[i]+=1
return summ
ob = Solution()
print(ob.numTilePossibilities("AAB"))입력
"AAB"
출력
8