문자열 조합 만들기(string combination)

팀장님이 개인적으로 필요하다며, 만들어 줄 수 있냐고 하셔서 급하게 만들어본 코드.

string instance를 substr을 통해 계속 생성해 사용하도록 되어있어, 개선의 여지가 있을 것 같다.

하지만, 이런 소소한 문제 해결에 행복감을 느끼게 되다니, 개인적으로도 내 자신이 안타깝다... oTL

다른 사람이 리뷰 좀 해 주면 좋겠다.

(Aug. 10 2016) 시간 복잡도 분석을 해 봤는데, M^(N-1)이 된다.

만약 10진수(M=10)에 대해, N = 1인 경우 1ms가 걸린다고 하면, N = 4 인경우 1초에 불과하지만, N = 9에 대한 모든 경우의 수를 만들려면 꼬박 하루가 지나고도 3시간 정도가 더 필요하며, N = 10인 경우에는 대략 11일이 걸린다. (만약 결과를 얻기 전에 stack overflow가 발생하지 않는다면 말이다...) -_-;

무시 무시한 구현인데, 모든 조합을 만들어 내려면 이것밖에 없는거 아닌가?@.@

N - 입력 문자열 가운데 x의 개수

      ex) 010-7x0x-00xx의 경우 N = 4

M - 조합에 사용할 문자 집합의 크기(개수)

      ex) 10진수 인 경우 M = 10, 알파벳 대문자의 경우 M = 26

#include <iostream> #include <fstream> #include <string> #include <algorithm> #include <cctype> void bar(std::string& front, std::string& end, std::ostream& out) { if (end.empty()) { out << front << std::endl; return; } auto pos = end.find('x'); if (pos == std::string::npos) { bar(front + end, std::string(), out); } else { for (int i = 0; i < 10; ++i) { bar(front + end.substr(0, pos).replace(pos, 1, std::to_string(i)), end.substr(pos + 1, end.length()), out); } } } void foo(std::string& input, std::ostream& out = std::cout) { std::for_each(input.begin(), input.end(), [](char& c) { c = std::tolower(c); }); auto pos = input.find('x'); if (pos == std::string::npos) { out << input << std::endl; return; } for (int i = 0; i < 10; ++i) { bar(input.substr(0, pos).replace(pos, 1, std::to_string(i)), input.substr(pos + 1, input.length()), out); } } int main(int argc, char** argv) { if (argc != 2) { std::cerr << argv[0] << " 010-7x0x-00xx" << std::endl; return 0; } foo(std::string(argv[1]), std::ofstream("list.txt")); return 0; }