[백준] 1759번: 암호 만들기 (Java)

💡문제 분석 요약

암호의 알파벳 개수 L과 사용한 문자의 종류 C를 입력받아서, 가능성 있는 암호들을 모두 구하는 문제이다.

• 시간 제한: 2초
• 메모리 제한; 128MB

 

💡알고리즘 설계

• C개의 문자열을 오름차순으로 `alpha` 배열에 저장하고, 자음&모음의 여부를 `check` 배열에 저장한다.
• start를 0부터 백트래킹을 시도한다.
• 백트래킹 메서드
  • 매개 변수로 `start` (시작위치), `length` (암호 길이)를 받는다.
  • `length` 가 L이면
    • 암호의 모음, 자음 최소 개수 조건을 확인하고, `result` 에 추가한다.
      (중복 방지를 위해 `LinkedHastSet` 타입으로 `result` 를 정의함)
  • start부터 C-1까지 작업을 수행한다.
    • `password[length]` 에 현재 위치의 알파벳을 넣는다.
    • 현재 위치의 알파벳의 자음, 모음 여부를 확인하고 count+1 한다. (`vo++` 또는 `con++`)
    • “현재 위치”와 “현재 길이+1” 로 메서드를 재귀 호출한다.
    • 자음&모음 count를 -1 하여 원상 복구한다.

 

💡코드

import java.io.*;
import java.util.*;

public class Main {
    static int L, C;
    static char[] alpha, password;
    static boolean[] check;
    static int vo, con;
    static LinkedHashSet<String> result = new LinkedHashSet<>();

    static void backTrack(int start, int length) {
        if(length == L) {
            if(vo >= 1 && con >= 2) {
                String s = new String(password);
                result.add(s);
            }
            return;
        }

        for(int i=start; i<C; i++) {
            password[length] = alpha[i];
            if(check[i]) con++; else vo++;
            backTrack(i+1, length+1);
            if(check[i]) con--; else vo--;
        }
    }

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        String[] input = br.readLine().split(" ");
        L = Integer.parseInt(input[0]);
        C = Integer.parseInt(input[1]);
        alpha = new char[C];
        check = new boolean[C];
        password = new char[L];
        String[] alpha_input = br.readLine().split(" ");
        Arrays.sort(alpha_input);
        for(int i=0; i<C; i++) {
            char ch = alpha_input[i].charAt(0);
            alpha[i] = ch;
            if(ch=='a' || ch=='e' || ch=='i' || ch=='o' || ch=='u') {
                check[i] = false; // 모음
            }
            else check[i] = true; // 자음
        }

        backTrack(0, 0);
        for(String s : result) {
            System.out.println(s);
        }
    }
}

 

💡시간복잡도

암호의 각 위치 L마다 C개의 문자 중 하나를 선택할 수 있으므로 $O(C^L)$이다.

 

💡 느낀점 or 기억할정보

이번에도 다른 풀이를 참고하지 않고 한 번에 맞출 수 있었다.

백트래킹 문제를 처음 풀었을 때보다는 발전한 것 같아서 뿌듯하다.