BOJ_암호만들기_1759

BOJ 1759번 암호만들기입니다.

문제는 아래와 같습니다.

문제에서 모음은 최소 한 개 이상 자음은 최소 두 개 이상 사용해서 여러 종류의 암호를 만들라고 하였으므로,

우선 현재까지 만들어진 암호 방식이 모음을 최소 한 개 이상 사용하였고, 자음을 최소 두 개 이상 사용했는지 체크해야 한다.

이 전에 BFS에서 해당 노드를 방문했는지 여부를 파악했던 boolean 배열을 만들거나 boolean값을 반환하는 

함수를 만들면 된다.

다음으로는 재귀 함수로 돌아갈 함수를 만들어야한다.

구조를 생각해보자

입력 받은 알파벳이 하나씩 패스워드에 입력되면서 재귀 함수가 돌아갈 것이고, 4자리의 암호를 만들려고 했기 때문에

만들어진 패스워드의 길이가 4자리가 맞고 모음 1개 이상 , 자음 2개 이상이 맞다면 출력하도록 구현하면 됩니다.

따라서 다음과 같은 함수를 만들어야 합니다.

private static int solution(int n, String[] element , String password , int i){

      // 4자리 패스워드를 만들기 위해 만들어진 함수로 n은 4자리가 맞는지를 체크하는 변수이다.

// element는 메인 함수에서 입력받은 문자들을 담아 둔 배열로, 하나씩 패스워드에 넣어가면서 비교한다.

// password는 solution 함수가 재귀로 돌면서 계속해서 변해가는 비밀번호로, 조건에 맞다면 다음 패스워드가 출력될 것이다.

// i는 사용자가 입력한 알파벳이 들어간 배열의 인덱스로, 하나씩 증가시키면서 패스워드를 바꿔간다.

}

여기서 중요한 것은 종료 조건과 답으로 나올 조건입니다.

생각을 해 보면 입력 받은 배열의 인덱스를 가르키는 i가 0부터 시작하기 때문에 element 배열의 사이즈보다는 작아야합니다.

따라서 다음과 같은 종료조건이 만들어질 수 있습니다.

if( i >= element.length ) return;  // Nothing to show;

그 다음 답으로 나올 조건은 패스워드의 길이가 n과 같아야 할 때 해당 패스워드가 모음 1개 이상 자음 2개 이상 

가지고 있는 지를 판단하는 것이다.

if( n == password.length() ) {

if( check(password)) {

System.out.println(password);

}

}

그 다음으로 solution이라는 함수를 재귀로 돌려야 하기 때문에 다음과 같은 연산 이 후에는 다시 solution 함수를 호출해야 한다.

단, 호출할 때에는 element의 배열에 있는 인덱스값이 하나씩 증가시켜서 다음 알파벳 요소를 가져올 수 있도록 구현한다.

또한 추가로 패스워드의 길이가 4 미만일 경우 알파벳을 더해서 solution 함수를 다시 호출해야 하므로 password에 element[i]를 더한 다음에 solution함수를 호출한다.

---

[solution 코드]

private static void solution(int n, String[] alpha, String password, int index) {

// n은 암호의 길이 (최종)

// alpha는 입력받은 알파벳들을 가지고 password에 넣을 예정

// password는 지금까지 만든 비밀번호

// index는 알파벳 인덱스를 가지고 알파벳을 사용할 지 말 지 고민

if (n == password.length()) {

if (check(password)) { // 모음 1개 이상, 자음 2개 이상이 맞다면 이게 답임

System.out.println(password);

}

return;

}

if (index >= alpha.length)

return;

solution(n, alpha, password + alpha[index], index + 1); // 다음 꺼 가져와야 하므로 index는 하나 증가

solution(n, alpha, password, index + 1); // 값을 사용하지 않기 때문에 alpha[index]를 안더해줌.

}

[모음 1개 이상 , 자음 2개 이상인지 파악하는 boolean 함수 : check]

// 모음은 1개 이상 , 자음은 2개 이상이 맞는지 체크하는 함수

private static boolean check(String password) {

int vowel_size = 0; // 모음 사이즈

int cons_size = 0; // 자음 사이즈

for (int i = 0; i < password.length(); i++) {

if (password.charAt(i) == 'a' || password.charAt(i) == 'i' || password.charAt(i) == 'o'

|| password.charAt(i) == 'u' || password.charAt(i) == 'e') {

vowel_size += 1;

} else {

cons_size += 1;

}

}

return (vowel_size >= 1 && cons_size >= 2); // 조건에 만족하면 true 반환 , 불만족 하면 false 반환

}

[메인 함수]

public static void main(String[] args) {

// TODO Auto-generated method stub

scanner = new Scanner(System.in);

int L = scanner.nextInt(); // 암호로 만들 숫자의 갯수

int C = scanner.nextInt(); // 전체 알파벳에서 뽑을 숫자

// 예시로는 L이 4 C는 6으로 나옴

// 여기서 C의 갯수 만큼 알파벳을 적은 뒤, 모음과 자음을 나눠서 배열에 입력할 것

test = new String[C];

vowel = new ArrayList<>();

consonant = new ArrayList<>();

for (int i = 0; i < C; i++) {

test[i] = scanner.next();

}

Arrays.sort(test); // 오름차순 정리 완료

solution(L,test,"",0);

}

---

이렇게 진행하면 출력으로 나와야 할 결과가 나옵니다.

추가로 모든 경우를 나열하는 것이 아니라, 경우의 수가 몇 개 인지 파악하는 것은 아래 코드와 같습니다.

피보나치 함수를 사용해서 계산한 것인데, 사실 위에 갯수는 14개가 나옵니다.

입력으로 a , c , i , s , t , w 를 받았고, 여기서 모음은 a,i 이고 자음은 c,s,t,w 입니다.

모음은 최소 한 개 이상 , 자음은 최소 2개 이상 이기 때문에

경우의 수는 모음이 한 개 또는 모음이 두 개 일 때 자음의 갯수로 파악할 수 있습니다.

이는 수학에서의 C (콤비네이션) 과 같은데 경우의수로 나올 수 있는 갯수는 아래와 같습니다.

[모음이 하나 사용될 때, (자음은 최소 2개 이상) 

+ 4자리 수이기 때문에 뽑는 숫자의 총 갯수 합은 4가 되어야함

2C1 * 4C3 = 8

[모음이 두 개 사용될 때, (자음은 최소 2개 이상) 

+ 4자리 수 이기 때문에 뽑는 숫자의 총 갯수 합은 4가 되어야함

2C2 * 4C2 = 6 

두 경우의 합은 14가지 . 이렇게 결과가 나오게 됩니다.

피보 나치 수열 함수는 아래와 같습니다.

---

private static int fibonacci(int n, int count) {

if (n == 0)

return 0;

if (n == 1)

return 1;

if (count >= 1)

return n * fibonacci(n - 1, count - 1);

else

return 1;

}

---

살짝 다른 점이 있다면 count라는 값을 넣어 준 것입니다.

이는 4C2 일 경우 분자의 4*3만을 뽑아내기 위해서 만든 변수입니다.

호출은 다음과 같습니다.

---

int ans = 0;

System.out.println((fibonacci(2, 1) / fibonacci(1, 1)) * (fibonacci(4, 3) / fibonacci(3, 3)));

System.out.println((fibonacci(2, 2) / fibonacci(2,2)) * (fibonacci(4, 2) / fibonacci(2, 2)));

ans += (fibonacci(2, 1) / fibonacci(1, 1)) * (fibonacci(4, 3) / fibonacci(3, 2))
                + (fibonacci(2, 2) / fibonacci(2,2)) * (fibonacci(4, 2) / fibonacci(2, 1));

---

다음과 같이 구현한다면 경우의 수도 나오게 됩니다.

그리고 주의할 점은 분모에서의 팩토리얼은 어차피 1까지 모두 곱하는 것이기 때문에 부담없이 구현하면 됩니다.