1759-암호만들기

l개의 알파벳 소문자로 구성된 비번 찾기. 이 때 암호 후보 알파벳들은 c가지 있음.

비번은

• 최소 1개의 모음

• 최소 2개의 자음

• 사전순 정렬.

가능성 있는 암호 모두 출력.

브루트포스 느낌. 경우의 수를 구해서 브루트포스 할 수 있나 보자.

(3<=l,c<=15)

최대 15C3 = 910.. 대략 1000개 정도 될듯. 걍 브루트포스 고고

int pwLen, alphaLen;
char alpha[15];

bool isSatisfyPwCondition(string pw) {
    bool isMo = false;
    int jaCount = 0;

    for(int i = 0; i<pw.length(); i++){
        if(pw[i] == 'a' || pw[i] == 'e' || pw[i] == 'i' || pw[i] == 'o' || pw[i] == 'u') {
            isMo = true;
        } else {
            jaCount += 1;
        }
    }

    if(isMo && jaCount >= 2) {
        return true;
    }
    return false;
}

// task
// 하나씩 선택하며 붙이기
void appendAlpha(int index, string pw) {
    if(index > alphaLen) {
        return;
    } else if (pw.length() == pwLen) {
        // 조건에 부합하면 춫력
        if(isSatisfyPwCondition(pw)) {
            cout<<pw<<endl;
        }
        return;
    }

    appendAlpha(index + 1, pw+alpha[index]);
    appendAlpha(index + 1, pw);
}


int main(int argc, const char * argv[]) {

    cin>>pwLen>>alphaLen;

    for(int i = 0; i<alphaLen; i++){
        cin>>alpha[i];
    }

    sort(alpha, alpha+alphaLen);

    appendAlpha(0, "");

    return 0;
}

boj 풀이

go(n, alpha, password, i)

• n: 만들어야 하는 암호 길이

• alpha: 사용할 수 있는 알파벳

• password: 현재까지 만든 암호

• i: 사용할지 말지 결정해야 하는 알파벳의 인덱스.

• 불가능한 경우

• 더 이상 선택할 수 있는게 없어서 함수 호출 불가.

  • i>=alpha

• 정답을 찾은 경우

  • password의 길이 = n

• 다음경우 호출

  • i번째 알파벳 사용 : go(n, alpha, password+alpha[i], i+1)

  • i번쨰 사용 안함 : go(n, alpha, password, i+1)

void go(int n, vector<char> &alpha, string password, int i) {
  if(passworld.length() == n) {
    if(check(password)) {
      cout<<password<<endl;
    }
    return;
  }
  if(i >= alpha.size()) return;

  go(n, alpha, password+alpha[i], i+1)
  go(n, alpha, password, i+1)
}

review

C++에서 string을 index로 접근할 경우 char& 타입으로 리턴.

• 순환함수에서 index를 전달하여, 다음 선택할 알파벳에 대한 정보를 전달.

  • 순환함수 호출시 다음에 사용할 index를 전달: appendAlpha(index + 1, pw+alpha[index]);

  • basecase의 조건문은 순환함수에서 호출되는 index가 알파벳 길이와 같을 때 리턴. 왜냐면 0부터 index시작이라 더이상 진행할 alpha배열의 값이 없기때문.

    if(index >= alphaLen) {
        return;
    }
  • 근데 이렇게 할 경우, 내가 순환함수에 index를 다음 index를 보내기 때문에 alphaLen이 6일 경우, 마지막 index를 호출할 경우(appendAlpha(6, "abch")), abch에 대해 조건 검사 해야되는데 6이라서 여튼 리턴하고 종료함. 여튼 내가 index에 현재 진행되는 index가 아닌 다음 index를 보내기 때문에 조건문을 수정해야함.

    (>=가 아닌 >)

    if(index > alphaLen) {
        return;
    }

와 근데 boj 설명 보니, 걍 정답의 if문을 먼저 거치게 하고, size 체크를 다음에 하면됨...

• 2개의 조건을 충족하기 때문에.. 순서만 바꿔주면 된거임 ㅠㅠ