JavaScript로 문자열의 모든 고유 순열(Permutation) 생성하기

문제 설명

문자열 str을 매개변수로 받아 처리하는 JavaScript 함수를 작성해야 합니다. 이 함수는 입력 문자열로 만들 수 있는 모든 순열(permutation)을 생성하되, 중복되는 결과가 있다면 반드시 제거해야 합니다.

즉, 문자열을 구성하는 모든 문자를 가능한 모든 순서로 재배치하여, 서로 겹치지 않는 고유한 조합들만 반환하는 것입니다.

예제 코드

다음은 이 문제를 해결하는 전체 코드입니다.

const str = 'aabb';
const permute = (str = '') => {
    if (!!str.length && str.length < 2){
        return str
    }
    const arr = [];
    for (let i = 0; i < str.length; i++){
        let char = str[i]
        if (str.indexOf(char) != i)
            continue
            let remainder = str.slice(0, i) + str.slice(i + 1, str.length)
            for (let permutation of permute(remainder)){
                arr.push(char + permutation)
            }
    }
    return arr
}
console.log(permute(str));

동작 원리

코드가 작동하는 방식을 단계별로 살펴보겠습니다.

1. 기저 조건(Base Case) 처리

문자열의 길이가 2 미만이면 더 이상 순서를 바꿀 수 없으므로, 해당 문자열을 그대로 반환합니다.

2. 중복 문자 건너뛰기

각 위치의 문자를 순회할 때 str.indexOf(char) != i 조건으로 현재 문자가 앞에서 이미 한 번 선택되었는지 확인합니다. 같은 문자가 여러 개 있어도 처음 등장한 위치에서만 분기를 수행하기 때문에, 중복된 순열이 처음부터 생성되지 않습니다.

3. 재귀 호출로 순열 조합

현재 선택한 문자를 제외한 나머지 부분(remainder)에 대해 자기 자신을 재귀적으로 호출하고, 반환된 각 순열 앞에 현재 문자를 붙여 결과 배열에 추가합니다.

실행 결과

위 코드를 실행하면 다음과 같은 콘솔 출력을 확인할 수 있습니다.

[ 'aabb', 'abab', 'abba', 'baab', 'baba', 'bbaa' ]

입력 문자열 'aabb'에는 같은 문자가 두 개씩 포함되어 있어, 중복을 허용한다면 24개(4!)의 순열이 나오지만, 이 알고리즘은 중복을 제거하여 정확히 6개의 고유한 순열만 반환합니다.