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

🔺 문제

1759번: 암호 만들기

 

 

🔺 코드

import java.util.*;
import java.io.*;
 
public class Main {
    static int L, C;
    static String[] inputArr;   // 전체 문자가 저장된 배열
    static String[] strArr;     // 뽑은 문자들을 저장할 배열
    
    static StringBuilder sb = new StringBuilder();  // 출력용
    
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine(), " ");
        
        L = Integer.parseInt(st.nextToken());
        C = Integer.parseInt(st.nextToken());
        
        inputArr = new String[C];
        strArr = new String[L];
        
        st = new StringTokenizer(br.readLine(), " ");
        for(int i = 0 ; i < C ; i++) {
            inputArr[i] = st.nextToken();
        }
        Arrays.sort(inputArr); // 오름차순 정렬
        
        combination(0, 0, 0, 0);
        System.out.println(sb);
    }
    
    // start : 탐색 시작 인덱스 위치
    // cnt : 카운트 직전까지 뽑은 조합에 포함된 수 갯수
    private static void combination(int start, int cnt, int mo, int za) {
        // [메소드 종료 조건]
        if(cnt == L) {
            // 최소 1개의 모음 (aeiou) & 최소 2개의 자음
            if(mo >= 1 && za >= 2) {
                for(int i = 0 ; i < strArr.length ; i++) {
                    sb.append(strArr[i]);
                }
                sb.append("\n");
            }
            
            return;
        }
        
        // 브루트포스 (inputArr 배열의 모든 수 시도)
        // start부터 처리하면 중복 수 추출 방지 & 순서가 다른 조합 추출 방지
        for(int i = start ; i < C ; i++) {
            if(inputArr[i].equals("a") || inputArr[i].equals("e") || inputArr[i].equals("i") || inputArr[i].equals("o") || inputArr[i].equals("u")) {
                strArr[cnt] = inputArr[i];
                combination(i + 1, cnt + 1, mo + 1, za);    // 다음 숫자 뽑으러 가기
            }
            else {
                strArr[cnt] = inputArr[i];
                combination(i + 1, cnt + 1, mo, za + 1);    // 다음 숫자 뽑으러 가기
            }
        }
    }
}
 

✅ 해결 아이디어
✔ 백트래킹 활용한 조합 구현 + 브루트포스

 

---

🔺 다른 풀이들

- 암호가 될 수 있는 문자들 입력을 char형으로 받으셨고,

  암호 조합을 만들 때 String ""에 +로 붙이는 식으로 만드는 식으로 하셨다.

로그인

 

 

-  내 코드랑 해당 문자가 모음인지 자음인지 확인해서 갯수 세는 타이밍이 좀 다르다. (대부분 이 순서로 푸셨다.)

[JAVA]백준 1759번: 암호 만들기

코드 확인하기

import java.io.*;
import java.util.*;
 
public class Main {
 
    public static int L, C;
    public static char[] list, code;
 
    public static void main(String[] args) throws IOException {
 
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        StringBuilder sb = new StringBuilder();
 
        StringTokenizer st = new StringTokenizer(br.readLine());
 
        L = Integer.parseInt(st.nextToken());
        C = Integer.parseInt(st.nextToken());
 
        list = new char[C];
        code = new char[L];
 
        st = new StringTokenizer(br.readLine());
        for (int x = 0; x < C; x++) {
            list[x] = st.nextToken().charAt(0);
        }
 
        Arrays.sort(list);
        makeCode(0, 0);
 
    }
 
    public static void makeCode(int start, int idx) {
        if (idx == L) {
            // 최소 1개의 모음, 최소 2개의 자음인지 확인
            if (isValid()) {
                System.out.println(code);
            }
            return;
        }
        
        for (int i = start ; i < C ; i++) {
            code[idx] = list[i];
            makeCode(i + 1, idx + 1);
        }
    }
 
    // 최소 모음 1개, 최소 자음 2개인지 확인
    public static boolean isValid() {
        int mo = 0;
        int ja = 0;
 
        for (char x : code) {
            if (x == 'a' || x == 'e' || x == 'i' || x == 'o' || x == 'u') {
                mo++;
            } else {
                ja++;
            }
        }
 
        if (mo >= 1 && ja >= 2) {
            return true;
        }
        return false;
    }
 
}

 

 

- visited 배열을 사용하셨다.

[자바] 백준 : 1759 암호만들기 (브루트포스 + 백트래킹 조합) 풀이 및 문제 접근법 / 유사 문제

---

💬 느낀 점

이번주 조합 문제를 많이 풀어보고

내것으로 만들어보겠다......💪💪💪💪

 

복습도 많이 해보겠다....

 

 

1회독	2회독	3회독	4회독	5회독
V

---

(참고)

✔ 백트래킹 활용한 조합 구현 방법 참고

[알고리즘] 순열, 중복 순열, 조합, 중복 조합 - 자바