백준 6443 - 애너그램
문제
씬디는 애너그램(anagram) 프로그램을 만들어 줄 수 있는 남자를 좋아한다. 참고로 씬디는 매우 예쁘다.
애너그램 프로그램이란, 입력받은 영단어의 철자들로 만들 수 있는 모든 단어를 출력하는 것이다. 가령 “abc” 를 입력받았다면, “abc”, “acb”, “bac”, “bca”, “cab”, “cba” 를 출력해야 한다.
입력받은 단어내에 몇몇 철자가 중복될 수 있다. 이 경우 같은 단어가 여러 번 만들어 질 수 있는데, 한 번만 출력해야 한다. 또한 출력할 때에 알파벳 순서로 출력해야 한다.
입력
첫째 줄에 단어의 개수 N 이, 둘째 줄부터 N개의 영단어가 들어온다. 영단어는 소문자로 이루어져 있다.
출력
N개의 영단어에 대한 모든 가능한 애너그램을 출력한다. 각각의 영단어에 대한 애너그램을 출력할 때, 알파벳 순서로 중복되지 않게 출력한다.
백준 코딩 테스트 가운데 가장 스트레스 받았던 문제. 분명 코드상으론 문제가 없는 거 같은데 답은 엉뚱한 게 나온다. ㅁㅊ….
일단 통과한 코드부터.
리스트(l)가 인자로 주어지면 해당 리스트의 다음 순열을 리턴해주는 함수(permutation)를 먼저 만든다. 이제 입력받은 문자열을 오름차순 정렬한 리스트로 변환해 출력한 뒤 함수에 인자로 넣고, 리턴값을 다시 출력한 뒤 함수에 인자로 넣고… 마지막 순열까지 반복했다. 통과.
def permutation(l):
n = len(l)
k = -1
for i in range(n-1, 0, -1):
if l[i-1] < l[i]:
k = i-1
break
if k == -1:
return -1
else:
for j in range(n-1, k, -1):
if l[k] < l[j]:
l[k], l[j] = l[j], l[k]
break
res = l[:k+1] + sorted(l[k+1:])
return res
for _ in range(int(input())):
w = sorted(input())
print(*w, sep='')
while True:
p = permutation(w)
if p == -1:
break
print(*p, sep='')
w = p
그런데 이해할 수 없다. 비슷한 방식을 곧바로 출력하는 대신 리스트(arr)에 넣고 최종 리스트를 출력하려 하니, 리스트에 뜻대로 다음 순열이 차곡차곡 쌓이지 않는다. 뭐가 문제인지 아직도 모르겠다.
처음 작성한 코드.
def permutation(l):
n = len(l)
k = -1
for i in range(n-1, 0, -1):
if l[i-1] < l[i]:
k = i-1
break
if k == -1:
return -1
else:
for j in range(n-1, k, -1):
if l[k] < l[j]:
l[k], l[j] = l[j], l[k]
break
res = l[:k+1] + sorted(l[k+1:])
return res
for _ in range(int(input())):
arr = [sorted(input())]
while True:
p = permutation(arr[-1])
if p == -1:
break
arr.append(p)
[print(*i, sep='') for i in arr]
[문제 보기]