백준[1759] - 암호 만들기

문제

백준 1759 문제 보기

접근 방법

이번 문제는 백 트래킹을 활용해 문제를 풀 수 있다.

입력 받은 문자열을 오름 차순으로 정렬한 뒤 백 트래킹을 실시 한다.

조합을 통해 만들어 낸 문자열의 길이가 최종 길이와 같다면 문자열 중복을 set을 활용해 피한다.

코드

#include <iostream>
#include <vector>
#include <string>
#include <algorithm>
#include <set>
using namespace std;

int L, C;

vector<char> c_arr;
set<string> se;

void back_tracking(int idx, int cnt, string s) {
    // 문자열 길이가 최종 길이와 같다면
    if(cnt == L) {
        // 모음 갯수, 자음 갯수
        int chk1 = 0, chk2 = 0;
        // 알파벳 중복 체크
        int visited[27] = {0, };

        for(int i = 0; i < s.length(); i ++) {
            // 모음인 경우
            if(s[i] == 'a' || s[i] == 'e' || s[i] == 'i' || s[i] == 'o' || s[i] == 'u') {
                chk1 ++;
            }

            // 자음인 경우
            else {
                // 중복 자음이 아닌 경우 카운트 증가
                if(!visited[s[i]-'0'-48])
                    chk2 ++;
            }
        }
        // 모음이 하나 이상이고 서로 다른 자음이 2개이상 사용하면 set에 저장
        if(chk1 >= 1 && chk2 >= 2)
            se.insert(s);
        return;
    }

    for(int i = idx; i < C; i ++) {
        // 문자를 선택한 경우
        back_tracking(i + 1, cnt + 1, s + c_arr[i]);
        // 선택하지 않고 지나친 경우
        back_tracking(i + 1, cnt, s);
    }
}

int main() {
    cin >> L >> C;

    for(int i = 0; i < C; i ++) {
        char c;
        cin >> c;
        c_arr.push_back(c);
    }

    // 오름 차순으로 정렬
    sort(c_arr.begin(), c_arr.end());

    // 백 트래킹 시작
    back_tracking(0, 0, "");

    // set에 저장된 문자열 출력
    for(auto it = se.begin(); it != se.end(); it++) {
        cout << *it << endl;
    }

    return 0;
}