모음사전 - 프로그래머스, c++

 

 

- 문제 풀이

"완전 탐색"를 사용하는 문제였다.

 

 

- 코드

1. 처음에 제출한 코드는 다음과 같다.

완전탐색 중 순열을 이용했다. 

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

int solution(string word) {
    int answer = 0;
    
    
    //0-5까지의 수가 들은 벡터 만들어주기 (순열 생성에 사용)
    vector<int> alphabet;    
    for(int i=0; i<6; i++) {
        alphabet.push_back(i);
    }
    
    
    //주어진 문자열을 int형으로 바꿔 vector에 저장
    vector<int> v_word;
    for(int i=0; i<word.length(); i++) {
        if(word[i]=='A')
            v_word.push_back(1);
        else if (word[i]=='E')
            v_word.push_back(2);
        else if (word[i]=='I')
            v_word.push_back(3);
        else if (word[i]=='O')
            v_word.push_back(4);
        else if (word[i]=='U')
            v_word.push_back(5);
    }
    for(int i=word.size()-1; i<5; i++)
        v_word.push_back(0);
    
    
    //순열을 이용하여 사전의 몇 번째에 주어진 v_word가 나오는지 계산
    int count = 1;
    do{
        bool same = true;
        for(int i=0; i<5; i++) {
            if(alphabet[i]!=v_word[i]) {
                same = false;
                break;
            }
        }       
        if(same)
            answer = count;
        else 
            count++;
    }
    while(next_permutation(alphabet.begin(), alphabet.end()));
    
    
    return answer;
}

 

생각해보니 사전은 중복을 허용하므로 그냥 순열을 생성하는 것이 아닌 중복순열을 사용해야 했다.

순열을 사용하면 쉽게 계산할 수 있었는데, 순열 중에서도 중복순열을 사용해야 사전 순대로 값을 정렬할 수 있었다.

하지만 이 방법으로도 오류가 났다.

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


vector<int> v_word;
const int count = 1;
const int answer = 0;


void repeatPermutation(vector<char> vec, vector<char> perm, int depth) {
    if (depth == perm.size()) {
        //순열을 이용하여 사전의 몇 번째에 주어진 v_word가 나오는지 계산
        bool same = true;
        for(int i=0; i<5; i++) {
            if(vec[i]!=perm[i]) {
                same = false;
                break;
            }
        }       
        if(same) {
            answer = count;
            return answer;
        }
        else 
            count++;
        
        return;
    }
    
    for(int i = 0; i < vec.size(); i++) {
        perm[depth] = vec[i];
        repeatPermutation(vec, perm, depth + 1);
    }
}


int solution(string word) {
    const int r = 5;
    
    //0-5까지의 수가 들은 벡터 만들어주기 (순열 생성에 사용)
    vector<int> v = {'0', '1', '2', '3', '4', '5'};
    
    
    vector<int> perm(r);
    
    
    //주어진 문자열을 int형으로 바꿔 vector에 저장
    for(int i=0; i<word.length(); i++) {
        if(word[i]=='A')
            v_word.push_back(1);
        else if (word[i]=='E')
            v_word.push_back(2);
        else if (word[i]=='I')
            v_word.push_back(3);
        else if (word[i]=='O')
            v_word.push_back(4);
        else if (word[i]=='U')
            v_word.push_back(5);
    }
    for(int i=word.size()-1; i<5; i++)
        v_word.push_back(0);
    
    
    repeatPermutation(v, perm, 0); 
    
    
    return answer;
}

 

 

따라서 문제를 풀기 위해서는 

2. 하지만 현재 탐색해야 할 알파벳이 5개 밖에 안되므로 그냥 단순한 전체 탐색방법을 사용해도 되고,

3. DFS탐색을 구현해 해결하는 방법도 있었다.

 

 

그 중 dfs 탐색을 사용하는 방법으로 해결했다.

이 방법으로 다른 완전 탐색 문제들도 해결이 가능하고 코드도 간단하기 때문이다.

#include <string>
#include <vector>
using namespace std;

string words = "AEIOU";
int answer, count;

void dfs(string now, string target) {
    //탐색하고 있는 문자열 now가 원하는 목표의 문자열 target==word와 같다면 count값 저장해 return
    if(now==target)
        answer = count;
    
    //탐색할 단어 now의 길이는 5이하 여야함
    if(now.length()>5)
        return;
    
    //탐색 한 번 했으니 count 해주기
    count++;
    
    //for문을 통해 dfs 계속 실행하며 탐색
    for(int i=0; i<words.length(); i++) {
        dfs(now+words[i], target);
    }
}

int solution(string word) {
    
    //dfs 실행
    dfs("", word);
    
    return answer;
}

(코드 참고: https://nayoungs.tistory.com/entry/C-%ED%94%84%EB%A1%9C%EA%B7%B8%EB%9E%98%EB%A8%B8%EC%8A%A4-level2-%EB%AA%A8%EC%9D%8C%EC%82%AC%EC%A0%84)