프로그래밍 면접 문제 11: All Permutations of String
프로그래밍 면접 문제 11: All Permutations of String
이 글은 블로그 http://www.ardendertat.com/의 프로그래밍 면접에 대한 글을 번역한 글입니다.
프로그래밍 면접 문제 10 : Kth Largest Element in Array
제목이 모든걸 말해주는 그런 문제입니다. 이 문제는 면접 질문에 상당히 자주나오는 질문입니다. 문자열이 주어지면 그 문자열의 모든 순열을 생성하는 문제입니다.
이 문제는 처음 보면 어려워 보이지만, 실제로 로직을 파악한 후에는 상당히 쉬운 유형 문제입니다. 길이 N의 문자열이 주어지고 이 문자열을 이용해서 N-1의 길이의 순열을 생성해야한다고 가정해 보겠습니다. N의 길이를 갖는 모든 순열은 어떻게 생성할 수 있을까요? 작은 예제를 예로 들어서 실험해보면 도움이 될 수 있습니다. 주어진 문자열이 ‘LSE’하고 한다면, 길이 2를 가진 순열은 ‘SE’와 ‘ES’가 있습니다. 이때 문자 L을 어떻게 이 순열에 포함시킬 수 있을지 고민해 봐야합니다. 가능한 접근 방법은 두 문자열에서 가능한 모든 위치에 L 문자를 삽입합니다. 즉, 처음, 중간, 그리고 끝 위치에 삽입합니다. 따라서 문자열 ‘SE’의 경우 결과는 ‘LSE’, ‘SLE’, ‘SEL’가 됩니다. 또한 문자열 ‘ES’의 경우 결과는 ‘LES’, ‘ELS’, ‘ESL’이 됩니다. 문자 L을 두 문자열에서 가능한 모든 위치에 삽입해서 위와 같은 결과를 얻었습니다. 사실 이게 로직의 전부입니다. 이제 재귀 알고리즘을 사용해서 이를 구현할 수 있습니다. 문자열의 길이가 1이 될 때까지 재귀적으로 반복해서 첫번째 문자를 제거하면, 이 경우가 기본 경우가 되고 이로 인해서 얻은 결과가 문자열 그 자체가 순열이 됩니다(길이가 1인 문자열은 그 자체가 순열입니다). 그런 다음 위의 알고리즘을 적용해서 각 단계에서 제거한 문자를 재귀 연산의 결과로 얻은 문자열에서 가능한 모든 위치에 삽입하고 이를 반환합니다. 다음은 이 알고리즘을 구현한 코드입니다:
def permutations(word):
if len(word) <= 1:
return [word]
#get all permutations of length N-1
perms = permutations(word[1:])
char = word[0]
result = []
#iterate over all permutations of length N-1
for perm in perms:
#insert the character into every possible location
for i in range(len(perm) + 1):
result.append(perm[:i] + char + perm[i:])
return result
첫 번째 문자를 제거하고 길이 N-1의 순열을 얻을 때까지 재귀적으로 반복했습니다. 그런 다음 첫 번째 문자를 길이 N-1의 문자열에 삽입하고, 길이 N을 갖는 모든 순열을 결과로 얻었습니다. 이 알고리즘의 복잡도는, 길이 N의 문자열에는 N!개의 순열이 있기 때문에 O(N!)입니다. 따라서 이 결과는 효율적입니다. 하지만, 문자열의 길이가 10-12보다 긴 문자열에는 이 알고리즘을 적용하지 않는 것이 좋습니다. 시간이 아주 오래 걸릴 수 있습니다. 이 알고리즘이 비효율적이기 때문이 아니라, 본질적으로 순열의 갯수가 너무 많기 때문입니다.
이 문제는 면접 문제에서 가장 많이 나오는 문제 중 하나이기 때문에 매우 중요합니다.
