BOJ 1759 - 암호 만들기

https://www.acmicpc.net/problem/1759

1759번: 암호 만들기

 

처음에 이 문제를 풀때,

다음과 같은 제한조건들을 생각해보았다

 

1. 모음의 갯수가 한개 이상

2. 자음의 갯수가 두개 이상

3. 사전순(오름차순) 으로 정렬되야 한다

4. L 개의 문자를 다 탐색하면 백트래킹 탈출 조건으로 잡는다.

 

라고 생각해서 

처음엔 아래와 같이 코드를 짰었다.

 

- c++

#include <iostream>
#include <algorithm>
#define MAX 16
 
using namespace std;
 
int L, C;
char vowels[5] = {'a', 'e', 'i', 'o', 'u'};
char arr[MAX];
char combi[MAX];
 
bool checked()
{
    for (int i = 0; i < L; i++)
    {
        char ch = combi[i];
        for (int j = 0; j < 5; j++)
        {
            if (ch == vowels[j])
            {
                return true;
            }
        }
    }
    return false;
}
 
void dfs(int start, int depth)
{
    if (depth == L && checked())
    {
        for (int i = 0; i < L; i++)
        {
            cout << combi[i];
        }
        cout << '\n';
        return;
    }
 
    for (int i = start; i < C; i++)
    {
        combi[depth] = arr[i];
        dfs(i + 1, depth + 1);
    }
}
 
int main()
{
    cin.tie(nullptr);
    ios_base::sync_with_stdio(false);
 
    cin >> L >> C;
 
    for (int i = 0; i < C; i++)
    {
        cin >> arr[i];
    }
    
    sort(arr, arr + C);
 
    dfs(0, 0);
 
    return 0;
}

 

 

 

문자가 어차피 3 <= L <= C <= 15 이기 때문에

위의 조건에서 그냥 모음 최소 하나 이상이면 자음 두개이상도 당연히 만족한다고 생각하고 위와 같이 짰으나

위의 경우 모음 2개 자음 1개의 경우도 있으며, 

모음 탐색시 O(N^2) 이어서 좋은 코드가 아니었다.

 

그래서 어떻게 고칠까 오랜 시간 고민을 하다가

답이 안나와서 

아래 블로그의 답을 보게 되었다.

 

http://melonicedlatte.com/algorithm/2018/09/10/203059.html

[백준] 1759번 C/C++ 풀이 _ 암호 만들기 - Easy is Perfect

 

- c++

#include <iostream>
#include <algorithm>
#include <vector>
#include <set>
#define MOEUM 5
#define MAX 16
 
using namespace std;
 
char arr[MAX];
set<char> moeum({'a', 'e', 'i', 'o', 'u'});
vector<char> dfs_vec;
int L, C;
 
void dfs(int depth, int moeum_num, int jaeum_num, int start)
{
    if (depth == L - 1)
    {
        if (moeum_num < 1 || jaeum_num < 2)
        {
            return;
        }
 
        for (int i = 0; i < L; i++)
        {
            cout << dfs_vec[i];
        }
        cout << '\n';
        return;
    }
 
    if (start >= C)
    {
        // start 가 범위 초과하면 종료
        return;
    }
 
    if (L - (moeum_num + jaeum_num) > C - start)
    {
        // 필요한 숫자 갯수 > 남은 숫자 갯수
        return;
    }
 
    for (int i = start; i < C; i++)
    {
        dfs_vec.push_back(arr[i]);
 
        if (moeum.find(arr[i]) == moeum.end())
        {
            // 자음일때
            dfs(depth + 1, moeum_num, jaeum_num + 1, i + 1);
        }
        else
        {
            // 모음일때
            dfs(depth + 1, moeum_num + 1, jaeum_num, i + 1);
        }
 
        dfs_vec.pop_back();
    }
}
 
int main()
{
    cin.tie(nullptr);
    ios_base::sync_with_stdio(false);
 
    cin >> L >> C;
 
    for (int i = 0; i < C; i++)
    {
        cin >> arr[i];
    }
 
    sort(arr, arr + C);
 
    for (int i = 0; i < C; i++)
    {
        dfs_vec.push_back(arr[i]);
 
        if (moeum.find(arr[i]) == moeum.end())
        {
            // 자음인 경우
            dfs(0, 0, 1, i + 1);
        }
        else
        {
            // 모음인 경우
            dfs(0, 1, 0, i + 1);
        }
 
        dfs_vec.pop_back();
    }
}

 

 

STL set 을 써서 모음 탐색에 대한 부분을 더 시간을 줄였다는 것,

그리고, 자음 갯수, 모음 갯수를 정확히 세고 있다는 점,

dfs 수행시 탈출 조건을 

start 가 범위(C) 를 초과했을때 탈출하는것,

필요 숫자의 갯수보다 남은 숫자의 갯수가 더 크면 탈출하는것

들을 추가했다는게 더 정확한 포인트였다.

 

이런 종료 조건을 명확히 해야 한다는 것을 

배울 수 있는 문제였다.

또한 문제에서 제시한 조건을 임의로 해석하기 보다는

있는 그대로 받아들이는 것이 중요함을 알게되었다.

 

 

*  또 다른 분들의 풀이를 봤는데

이분만한 풀이가 없는 것 같다

blog.naver.com/kks227/220786417910

백트래킹(Backtracking) (수정 2019-10-09)

 

- c++

#include <algorithm>
#include <cstdio>
 
using namespace std;
 
int l, c;
char input[16], encrypt[16];
bool is_vowel[26];
 
void backtracking(int idx, int prev, int consonant, int vowel) {
    if (idx == l) {
        if (consonant >= 2 && vowel >= 1) puts(encrypt);
        return;
    }
    
    for (int i = prev + 1; i < c; ++i) {
        encrypt[idx] = input[i];
        backtracking(idx + 1, i, consonant + !is_vowel[input[i] - 'a'], vowel + is_vowel[input[i] - 'a']);
    }
}
 
int main() {
    scanf("%d %d", &l, &c);
    for (int i = 0; i < c; ++i) scanf(" %c", input + i);
    sort(input, input + c);
    is_vowel[0] = is_vowel[4] = is_vowel[8] = is_vowel[14] = is_vowel[20] = true;
    backtracking(0, -1, 0, 0);    
    return 0;
}

 

 

 

설명도 나 같은 돌머리도 이해시킬 정도로 뛰어나고, 코드가 가장 깔끔한듯.

모음인지 자음인지 체크하는 것을 bool 배열을 사용해서 더해준다는것이 충격적이고

원래의 백트래킹 개념이라면 원 상태로 되돌려놔야 하나, 어차피 값을 덮어씌우므로, 굳이 원상태로 되돌리는 별도의 코드가 필요하지 않다는 점 등...

여러므로 가장 깔끔한 코드 같다.