[SWEA][D3][c++] 9480. 민정이와 광직이의 알파벳 공부

문제

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

 

문제 링크

https://swexpertacademy.com/main/code/problem/problemDetail.do?contestProbId=AXAdrmW61ssDFAXq

SW Expert Academy

 

풀이 과정

 

모든 단어의 조합에서 알파벳 a~z 까지를 다 가지고 있는지를 확인하는 방식으로 문제를 풀었습니다.

 

1.입력받은 단어를 vector에 넣는다.

2.DFS를 사용하여 alphabet배열에 입력받은 단어의 알파벳을 가지고 있는 위치의 수를 1더한다.

3.alphabet 배열을 체크하여 현재 a~z 까지를 다 가지고 있는지를 확인한다.

4.index에 1을 더하고 다시 DFS를 한다

5.2에서 더했던 알파벳들을 다시 다 빼준다.

6.모든 DFS가 끝난 후 결과를 출력한다.

 

코드

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

int alphabet[26];
vector<string> words;
int n;
int result;

//알파벳 넣기
void alphabetAdd(string s){
    for(int i=0; i<s.size();i++){
    	alphabet[s[i]-'a']++;
    }
}

//알파벳 빼기
void alphabetSub(string s){
    for(int i=0; i<s.size();i++){
    	alphabet[s[i]-'a']--;
    }
}

//알파벳 다있는지 확인
bool alphabetCheck(){
    for(int i=0; i<26;i++){
    	if(alphabet[i]<1)
            return false;
    }
    return true;
}

//모든 경우의 수 
void dfs(int index){
    if(index==words.size())
        return;
    
	for(int i=index; i<words.size(); i++){
        alphabetAdd(words[i]);
        if(alphabetCheck())
            result++;
        dfs(i+1);
        alphabetSub(words[i]);
    }
}

int main(int argc, char** argv)
{
	int test_case;
	int T;
	cin>>T;
    
 
	
    for(test_case = 1; test_case <= T; ++test_case)
	{
        result=0;
        memset(alphabet,0,sizeof(alphabet));
        words.clear();
        cin>>n;
        
        for(int i=0; i<n; i++){
        	string s;
            cin>>s;
            words.push_back(s);
        }
        dfs(0);
        
        cout<<"#"<<test_case<<" "<<result<<"\n";
        
	}
	return 0;
}