JavaScript에서 문자열 대소문자를 조합해 만들 수 있는 모든 순열 구하기

문제 설명

문자열 str을 첫 번째이자 유일한 인수로 받는 JavaScript 함수를 작성해야 합니다.

이 함수는 문자열 안의 모든 영문자를 개별적으로 소문자 또는 대문자로 변환하여 새로운 문자열을 만들 수 있으며, 이렇게 만들 수 있는 모든 가능한 문자열의 목록을 반환해야 합니다.

숫자나 특수문자는 대소문자 구분이 없으므로 원래 그대로 유지됩니다.

예를 들어 함수에 다음과 같은 입력이 주어졌다고 가정해 보겠습니다.

입력

const str = 'k1l2';

출력

const output = ["k1l2", "k1L2", "K1l2", "K1L2"];

영문자가 총 2개('k'와 'l')이고 각각 2가지 경우(대문자/소문자)를 가지므로, 결과는 2 × 2 = 4개의 문자열이 됩니다.

풀이 접근 방식

이 문제는 재귀(백트래킹) 기법으로 깔끔하게 해결할 수 있습니다. 핵심 아이디어는 다음과 같습니다.

문자열의 각 위치를 하나씩 순서대로 처리합니다.
현재 위치의 문자가 영문자라면, 소문자로 넣는 경우와 대문자로 넣는 경우 두 갈래로 나누어 재귀 호출합니다.
영문자가 아니라면(숫자, 특수문자 등) 해당 문자를 그대로 붙여 다음 위치로 진행합니다.
모든 문자를 다 처리하면 완성된 문자열을 결과 배열에 저장합니다.

예제 코드

다음은 위 접근 방식을 구현한 전체 코드입니다.

const str = 'k1l2';

const changeCase = function (S = '') {
    const res = [];
    const helper = (ind = 0, current = '') => {
        if (ind >= S.length) {
            res.push(current);
            return;
        }
        if (/[a-zA-Z]/.test(S[ind])) {
            helper(ind + 1, current + S[ind].toLowerCase());
            helper(ind + 1, current + S[ind].toUpperCase());
        } else {
            helper(ind + 1, current + S[ind]);
        }
    };
    helper();
    return res;
};

console.log(changeCase(str));

코드 상세 설명

1. 결과를 담을 배열 준비

배열 res는 최종적으로 반환될 모든 순열 문자열을 저장하는 역할을 합니다.

2. 재귀 헬퍼 함수

helper 함수는 두 개의 매개변수를 받습니다.

ind: 현재 처리 중인 문자열의 인덱스
current: 지금까지 만들어진 부분 문자열

인덱스가 문자열 길이 이상이 되면 하나의 완전한 조합이 완성된 것이므로, current를 res에 추가하고 재귀를 종료합니다.

3. 정규표현식으로 영문자 판별

/[a-zA-Z]/.test(S[ind])를 사용해 현재 문자가 알파벳인지 확인합니다. 알파벳이라면 toLowerCase()와 toUpperCase()를 각각 적용해 두 번의 재귀 호출을 수행하고, 그렇지 않다면 문자를 그대로 이어붙입니다.

출력 결과

[ 'k1l2', 'k1L2', 'K1l2', 'K1L2' ]

시간 복잡도

영문자가 n개라고 할 때, 각 문자마다 대문자와 소문자 두 가지 선택지가 존재하므로 총 2ⁿ개의 조합이 생성됩니다. 각 조합을 만드는 데 최대 O(n)의 연산이 필요하므로, 전체 시간 복잡도는 O(2ⁿ × n)입니다.