C++로 문자열 대소문자 순열 모두 생성하기

알파벳과 숫자가 섞여 있는 문자열이 있다고 가정해 봅시다. 이때 문자열에 포함된 각 알파벳을 대문자 또는 소문자로 변환하여 만들 수 있는 모든 가능한 조합(순열)을 생성해야 합니다. 만약 문자열에 숫자만 포함되어 있다면, 원본 문자열 그대로를 반환하면 됩니다.

예를 들어 입력 문자열이 "1ab2"라면, 결과는 다음과 같습니다.

["1ab2", "1Ab2", "1aB2", "1AB2"]

문제 접근 방법

이 문제는 재귀(recursion) 기법으로 효과적으로 해결할 수 있습니다. 핵심 아이디어는 다음과 같습니다.

• 재귀 함수는 현재 처리할 위치를 나타내는 인덱스(index)와, 지금까지 만들어진 임시 문자열(temp)을 매개변수로 받습니다.
• 인덱스가 문자열 길이와 같아지면, 지금까지 만든 임시 문자열을 결과 목록에 추가하고 재귀를 종료합니다.
• 현재 위치의 문자가 소문자라면 대문자로, 대문자라면 소문자로 바꾼 경우를 각각 재귀 호출하여 두 갈래로 탐색을 이어갑니다.
• 숫자나 특수문자는 변환하지 않고 그대로 붙여 한 갈래로만 진행합니다.

이렇게 하면 알파벳이 등장할 때마다 경우의 수가 두 배씩 늘어나며, 최종적으로 모든 대소문자 조합을 빠짐없이 얻을 수 있습니다.

구현 예제

아래 C++ 코드를 통해 실제 동작 방식을 확인해 보겠습니다.

#include <bits/stdc++.h>
using namespace std;
void print_vector(vector<string> v){
    cout << "[";
    for(int i = 0; i<v.size(); i++){
        cout << v[i] << ", ";
    }
    cout << "]"<<endl;
}
class Solution {
    public:
    vector <string> res;
    void solve(string s, int idx = 0, string temp = ""){
        if(idx == s.size()){
            res.push_back(temp);
            return;
        }
        solve(s, idx + 1, temp + s[idx]);
        int diff = 'a' - 'A';
        if(s[idx] >= 'a' && s[idx] <= 'z'){
            char x = (s[idx] - diff);
            solve(s, idx + 1, temp + x);
        }
        else if (s[idx] >= 'A' && s[idx] <= 'Z'){
            char x = (s[idx] + diff);
            solve(s, idx + 1, temp + x);
        }
    }
    vector<string> letterCasePermutation(string S) {
        res.clear();
        solve(S);
        return res;
    }
};
main(){
    Solution ob;
    print_vector(ob.letterCasePermutation("1ab2"));
    print_vector(ob.letterCasePermutation("9876"));
}

입력

"1ab2"
"9876"

출력

[1ab2, 1aB2, 1Ab2, 1AB2]
[9876]

출력 결과에서 볼 수 있듯이, "1ab2"의 경우 알파벳 a와 b의 대소문자 조합 4가지가 모두 생성되었으며, 숫자로만 이루어진 "9876"은 원본 문자열 하나만 반환됩니다.