[백준/c++] 1759번 : 암호 만들기

문제 링크 - https://www.acmicpc.net/problem/1759

[문제]

[풀이]

• 배열에 문자열을 입력받고, 배열을 정렬한다. (암호는 정렬된 문자열 이니까)
• 재귀함수를 통해 조건(모음,자음 갯수)를 만족하면서 길이가 L인 오름차순으로 된 문자열을 전부 찾는다
• func(index, start, l, c) 에서 index는 현재 문자열의 index, start는 다음 index에 올 문자의 시작지점, l은 암호의 길이, c는 주어진 문자열의 길이이다.
• 만약 테스트 케이스를 거치는 문제였다면 함수 매개변수에 arr(입력받은 문자열),answer(현재까지 만들어진 암호)도 넣어줘야 했을 것 같다.
• 재귀함수안에서 for문을 통해 정렬된 arr을 전부 돌면서 가능한 문자열의 경우를 answer[]에 넣는다.
• 중복체크를 하기위해 if(check[i])문으로 검사했지만 다음 재귀함수로 들어가는 부분에 func(index+1,i,l,c) 대신 func(index+1,i+1,l,c)를 실행한다면 중복되는 부분이 없어지므로 if문을 없애도 성립한다.
• 문자열이 길이 L만큼 만들어졌으면 for문을 통해 각문자의 모음,자음을 검사한다음 문제에 주어진 조건(모음,자음 갯수)에 부합하면 문자열을 출력하고, 부합하지 않으면 그냥 리턴한다.

[코드]

//1759번: 암호 만들기
#include <iostream>
#include <algorithm>
using namespace std;

int l,c;
char arr[16];
char answer[16]; 
bool check[16];
int vowel; //모음갯수
int consonant; //자음갯수



void func(int index,int start, int l, int c){
 
    if(index==l){
        vowel=0;
        consonant=0;

        for(int i=0; i<l; i++){
            if(answer[i]=='a'||answer[i]=='e'||answer[i]=='i'||answer[i]=='o'||answer[i]=='u')
            vowel++;
            else
            consonant++;
        }

        if(vowel>=1 && consonant>=2){
            for(int i=0; i<l; i++){
                cout<<answer[i];
            }
            cout<<"\n";
             return;
        }
        return;
            
        }
       
        //여기서, i=start하면 이전함수에서 i번째 였으니까 1번의 중복이 발생할 수 있지만
        //if(chekc[i])로 중복체크해주니까 상관없다.
        //또는 중복체크 안하고, 재귀함수 호출할때 func(index+1,i+1,l,c)이렇게 start에 i+1를 넣어주어도 된다.
        for(int i=start; i<c; i++){
            if(check[i])
            continue;

            check[i]=true;
            answer[index]=arr[i];
            //cout<<"answer["<<index<<"]: "<<answer[index]<<endl;
            func(index+1,i,l,c);
            check[i]=false;
            
        }
    }


int main(){
   cin>>l>>c;

   for(int i=0; i<c; i++){
       cin>>arr[i];
   }
    sort(arr,arr+c);
    // for(int i=0; i<c; i++){
    //     cout<<arr[i]<< " ";
    // }
    func(0,0,l,c);
}

[모르겠는 점]

• 중복인 경우를 제거해서 if문을 생략하고 하는 경우,아래와 같이 작성하면 정답이 잘 출력되는데
  
• 아래 코드처럼 func안에 i+1을 넣는대신 for문에 i=start+1로 시작하면 정답이 다르게 출력된다. 변수 start쓰는 부분이 for문에서밖에 없는데 왜 틀린답이 나오는지 모르겠다 .... 이유를 생각해봐야겠다.
  

[해결]

• main에서 func함수 호출하는 부분 살펴보면 func(0,0,l,c) 이렇게 호출하는데 이때 두번재 인자가 start에 해당한다.
• for문에서 i=start+1로 받아버리면 start를 0으로 초기화 해도 arr배열의 start+1(=즉 1)부터 돌기때문에 arr[0]에 해당하는 문자를 고려할 수 없다. (그래서 예제문제 출력에 c로시 시작하는 문자열 부터 출력되는 거였음!)
• 결론은 arr[0] 부터 전부 고려해야 하므로 start는0 부터 실행되게 해야하고, 재귀 호출하는 부분에서 i+1로 넣어주는게 맞다.