- 입력된 단어 W의 철자들만을 조합하여 만들 수 있는 모든 단어를 사전순으로, 중복 없이 출력하여야 한다.
- W의 각 철자들은 중복될 수 있다.
얼핏 보기엔 N과 M 문제와 비슷해 보이지만, 주어지는 입력의 각 요소가 서로 중복될 수 있다는 점이 가장 큰 차이라고 할 수 있다.
지금껏 풀어왔던 모든 조합을 사전순으로 출력하거나 추가적인 규칙이 붙는 문제와 큰 차이는 없을 것이라 판단하여, 일단 입력에 중복되는 철자가 없는 경우만을 대응하는 코드를 짜 보았다.
from sys import stdin
def search(string):
global visited, alphabets
if len(string) == len(alphabets):
print(string)
return
for i in range(len(alphabets)):
if not visited[i]:
visited[i] = True
search(string + alphabets[i])
visited[i] = False
alphabets = list(stdin.readline().rstrip())
alphabets.sort()
visited = [False for _ in range(len(alphabets))]
search("")
이 코드는 중복되는 철자가 없는 입력에는 잘 대응한다. 입력을 사전순으로 정렬하고, 모든 조합을 첫 번째 문자부터 재귀적으로 탐색한다. 예를 들어 입력이 "abc"인 경우
search("")
↳ search("a")
↳ search("ab")
↳ search("abc") -> abc
↳ search("ac")
↳ search("acb") -> acb
↳ search("b")
↳ search("ba")
↳ search("bac") -> bac
↳ search("bc")
↳ search("bca") -> bca
↳ search("c")
↳ search("ca")
↳ search("cab") -> cab
↳ search("cb")
↳ search("cba") -> cba
이상과 같은 과정을 통해 답을 산출한다.
이 프로그램에 "aab"와 같은 중복되는 철자가 있는 입력을 넣은 경우 어떻게 동작하는지를 보자. 가독성을 위해 첫 번째 a를 a1으로, 두 번째 a를 a2로 표기하겠다.
search("") ↳ search("a1") ↳ search("a1a2") ↳ search("a1a2b") -> a1a2b ↳ search("a1b") ↳ search("a1ba2") -> a1ba2 ↳ search("a2") ↳ search("a2a1") ↳ search("a2a1b") -> a2a1b ↳ search("a2b") ↳ search("a2ba1") -> a2ba1 ↳ search("b") ↳ search("ba1") ↳ search("ba1a") -> ba1a2 ↳ search("ba2") ↳ search("ba2a1") -> ba2a1
볼드 처리된 부분이 이미 출력되었던 문자열이 또 출력되는 경우인데, 이 부분을 살펴보면 바로 직전 호출과 같은 매개변수 문자열이 들어갔음을 발견할 수 있다. 따라서 나는 직전 호출과 같은 문자열이 매개변수로 들어오는 경우를 걸러냄으로써 중복을 제거하는 방법을 고안하였다.
from sys import stdin
def search(last_str, string):
global s, visited
if len(string) == len(s):
print(string)
return
for i in range(len(s)):
candidate = string + s[i]
if not visited[i] and candidate != last_str:
visited[i] = True
search(string, candidate)
visited[i] = False
last_str = candidate
n = int(stdin.readline())
while n:
s = list(stdin.readline().rstrip())
s.sort()
visited = [False for _ in range(len(s))]
search("", "")
n -= 1
코드 1과 다른 점은 매개변수로 이전 호출때의 문자열last_str
도 넘겨주고, 이를 현재 매개변수 문자열 string
과 비교하는 절차가 추가된 것이다.
여기까지 한 뒤 다른 사람들은 어떻게 풀었는지 찾아보았고, 이 풀이법보다 훨씬 간단하고 직관적인 방법을 발견하였다...
정렬 및 중복 여부와 관계없이, 각 철자의 출현 횟수만을 세어 그 만큼을 기존과 같은 방법으로 조합하여 출력하면 훨씬 간결하게 정답을 구할 수 있는 것이다.
from sys import stdin
ALPHABET_LEN = 26
def search(string):
global alpha
if len(string) == len_s:
print("".join(string))
return
for i in range(ALPHABET_LEN):
if alpha[i] != 0:
alpha[i] -= 1
search(string + [chr(i + ord('a'))])
alpha[i] += 1
n = int(stdin.readline())
while n:
len_s = 0
alpha = [0 for _ in range(ALPHABET_LEN)]
for i in stdin.readline().rstrip():
alpha[ord(i) - ord('a')] += 1
len_s += 1
search([])
n -= 1
문자열 비교 등의 고비용 연산이 빠졌지만 결국 똑같이 모든 경우를 탐색하는 코드이다보니, 주어진 범위에서의 코드 2와의 소요 시간 차이는 크지 않았다. 하지만 그것에 비해 훨씬 직관적이고 간결한 코드라고 생각된다.