[SWEA 9480][C++] 민정이와 광직이의 알파벳 공부(D3)

[문제보기]

민정이와 광직이의 알파벳 공부

SW Expert Academy

 

[풀이과정]

(1) search()

     이 함수는 각 고른 단어에 대해 모든 소문자 알파벳이 있는지 검사하는 함수이다.

 

(2) dfs(int idx, int cnt, int end)

     idx는 시작점을 결정하는 변수, cnt는 우리가 몇 개를 골랐는지 알려주는 변수,

     end는 우리가 골라야 하는 개수 변수

     이 세 개의 변수를 이용하여 재귀 함수를 통해 단어들 중에 한 개를 뽑은 경우, 두 개를 뽑은 경우,

     세 개를 뽑은 경우 , ... , 모든 단어를 뽑은 경우의 수를 모두 찾아서 search()로 넘긴다.

 

(3) main()

     마지막 for문에 대해서는 몇 개의 단어를 뽑을 건지 결정하는 for문이다.

 

[소스코드]

#include <iostream>
#include <cstring>
using namespace std;
int alpha[26];
string words[15];
bool check[15];
int n, ans;

void search(){
    memset(alpha, 0, sizeof(alpha));
    for(int i=0; i<n; i++){
        if(!check[i]){
            for(int j=0; j<words[i].size(); j++){
                alpha[words[i][j]-97]++;
            }
        }
    }

    for(int i=0; i<26; i++){
        if(alpha[i] == 0){
            return;
        }
    }
    ans++;
}

void dfs(int idx, int cnt, int end){
    if(cnt == end){
        search();
        return;
    }

    for(int i=idx; i<n; i++){
        if(!check[i])
            continue;
        check[i] = false;
        dfs(i, cnt+1, end);
        check[i] = true;
    }
}

int main(){
    cin.tie(0);
    cout.sync_with_stdio(false);

    int T;
    cin >> T;
    for(int test = 1; test <= T; test++){
        memset(check, true, sizeof(check));
        ans = 0;

        cin >> n;
        string s;
        for(int i=0; i<n; i++){
            cin >> s;
            words[i] = s;
        }

        for(int i=1; i<=n; i++){
            dfs(0, 0, i);
        }

        cout << "#" << test <<" " << ans << "\n" ;
    }
}

 

[해결과정 중 실수한 부분]

 맨 처음에는 string words에 대해서 초기화를 하기 위해 memset(words, 0, sizeof(words)) 함수를 넣어주었다.

 그러나, swea에서 runtime error가 나서 구글링을 해본 결과 memset으로 초기화를 해주는 경우는 int, bool자료형에

 대해 0 or 1, true or false와 같은 간단한 경우에만 초기화가 가능하다. 

 

 이 부분을 빼고 정답을 돌려봤을 때, 바로 pass가 나왔다.