여러가지/알고리즘 & 자료구조

[백준] 암호 만들기 - 1759번

hyeseong-dev 2024. 6. 13. 10:28

암호 만들기

2 초 128 MB 77884 37233 25516 44.782%

문제

바로 어제 최백준 조교가 방 열쇠를 주머니에 넣은 채 깜빡하고 서울로 가 버리는 황당한 상황에 직면한 조교들은, 702호에 새로운 보안 시스템을 설치하기로 하였다. 이 보안 시스템은 열쇠가 아닌 암호로 동작하게 되어 있는 시스템이다.

암호는 서로 다른 L개의 알파벳 소문자들로 구성되며 최소 한 개의 모음(a, e, i, o, u)과 최소 두 개의 자음으로 구성되어 있다고 알려져 있다. 또한 정렬된 문자열을 선호하는 조교들의 성향으로 미루어 보아 암호를 이루는 알파벳이 암호에서 증가하는 순서로 배열되었을 것이라고 추측된다. 즉, abc는 가능성이 있는 암호이지만 bac는 그렇지 않다.

새 보안 시스템에서 조교들이 암호로 사용했을 법한 문자의 종류는 C가지가 있다고 한다. 이 알파벳을 입수한 민식, 영식 형제는 조교들의 방에 침투하기 위해 암호를 추측해 보려고 한다. C개의 문자들이 모두 주어졌을 때, 가능성 있는 암호들을 모두 구하는 프로그램을 작성하시오.

입력

첫째 줄에 두 정수 L, C가 주어진다. (3 ≤ L ≤ C ≤ 15) 다음 줄에는 C개의 문자들이 공백으로 구분되어 주어진다. 주어지는 문자들은 알파벳 소문자이며, 중복되는 것은 없다.

출력

각 줄에 하나씩, 사전식으로 가능성 있는 암호를 모두 출력한다.

예제 입력 1 복사

4 6
a t c i s w

예제 출력 1 복사

acis
acit
aciw
acst
acsw
actw
aist
aisw
aitw
astw
cist
cisw
citw
istw

문제 이해

암호 만들기 문제는 주어진 문자들로 가능한 암호를 생성하는 문제입니다. 암호는 다음 조건을 만족해야 합니다.

  1. 암호는 서로 다른 L개의 알파멧 소문자로 구성됩니다.
  2. 최소 1개의 모음(a, e, i, o, u)과 최소 2개의 자음으로 구성되어야 합니다.
  3. 암호는 알파벳 순서대로 정렬된 문자열이어야 합니다.

입력

  1. 첫 줄에 두 정수 L, C가 주어집니다.
  2. 다음 줄에는 C개의 알파벳 소문자가 공백으로 구분되어 주어집니다. 이 알파벳은 중복되지 않습니다.

출력

  • 각 줄에 하나씩, 사전순으로 가능성 있는 암호를 모두 출력합니다.

예제 입력

4 6 
a t c i s w

예제 출력

acis
acit
aciw
acst
acsw
actw
aist
aisw
aitw
astw
cist
cisw
citw
istw

해결방법

  1. 입력 처리
  • L, C를 읽습니다.
  • C개의 문자를 char 배열로 만듭니다.
  1. 문자 정렬
  • char 배열을 오름차순으로 정렬합니다.
  1. 조합 생성
  • 주어진 문자들로부터 길이가 L인 모든 조합을 생성합니다.
  1. 유효한 암호 필터링
  • 각 조합에 대해 모음과 자음의 개수를 확인하여 유효한 암호인지 확인합니다.
  1. 출력
  • 사전순으로 출력합니다.

코드

package 암호만들기;

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.HashSet;
import java.util.Set;
import java.util.StringTokenizer;

public class Main {
    // 모음을 저장할 Set 초기화
    private static final Set<Character> vowels = new HashSet<>(Arrays.asList('a', 'e', 'i', 'o', 'u'));

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());

        // 입력값으로부터 L(암호 길이)과 C(문자 수)를 읽음
        int L = Integer.parseInt(st.nextToken());
        int C = Integer.parseInt(st.nextToken());

        // C개의 문자를 저장할 배열 생성
        char[] characters = new char[C];
        st = new StringTokenizer(br.readLine());
        for (int i = 0; i < C; i++) {
            characters[i] = st.nextToken().charAt(0);
        }
        Arrays.sort(characters); // 정렬하여 오름차순으로 만듦

        StringBuilder combination = new StringBuilder();
        generateCombinations(characters, L, 0, combination); // // 조합 생성 메서드 호출
    }

    // 조합을 생성하는 메서드
    private static void generateCombinations(char[] characters, int L, int start, StringBuilder currentCombination) {
        // 현재 조합의 길이가 L과 같으면 유효성 검사
        if (currentCombination.length() == L) {
            if (isValid(currentCombination)) {
                System.out.println(currentCombination); // 유효한 조합이면 출력
            }
            return;
        }

        // 주어진 char[] 배열에서 시작 인덱스부터 문자 선택
        for (int i = start; i < characters.length; i++) {
            currentCombination.append(characters[i]); // // 현재 문자 추가
            generateCombinations(characters, L, i + 1, currentCombination); // 다음 문자를 선택하여 재귀 호출
            currentCombination.deleteCharAt(currentCombination.length() - 1); // 마지막 문자 삭제하여 백트래킹
        }
    }

    // 주어진 조합이 유효한지 검사하는 메서드
    private static boolean isValid(StringBuilder password) {
        int numVowels = 0; // 모음 개수
        int numConsonants = 0; // 자음 개수

        // 조합의 각 문자를 검사
        for (int i = 0; i < password.length(); i++) {
            char ch = password.charAt(i);
            if (vowels.contains(ch)) {
                numVowels++; // 모음이면 모음 개수 증가
            } else {
                numConsonants++; // 자음이면 자음 개수 증가
            }
        }

        // 모음이 최소 1개 이상, 자음이 최소 2개 이상인지 확인
        return numVowels >= 1 && numConsonants >= 2;
    }
}

설명

main 메소드에서 StringBuilder와 generateCombinations 사용 이유

StringBuilder combination = new StringBuilder();
generateCombinations(characters, L, 0, combination); // 가능한 모든 조합을 생성

왜 사용하는가?

  • StringBuilder combination = new StringBuilder();
    • 현재까지 생성된 암호의 조합을 저장하는 역할을 합니다.
    • 문자열을 효율적으로 조작할 수 있게 해줍니다. StringBuilder는 String보다 빠르게 문자열을 추가하거나 제거할 수 있습니다.
  • generateCombinations(characters, L, 0, combination);
    • 모든 가능한 암호 조합을 생성하기 위해 재귀적으로 호출됩니다.
    • characters 배열, 목표 길이 L, 현재 시작 인덱스 0, 그리고 현재 조합을 저장하는 combination을 매개변수로 받습니다.

StringBuilder를 사용하는 이유

  • 효율성:
    • StringBuilder는 내부적으로 가변 길이 배열을 사용하여 문자열을 관리합니다. 문자열을 추가하거나 삭제할 때 새로운 문자열 객체를 생성하지 않으므로 성능이 뛰어납니다.
    • 재귀 호출과 백트래킹 과정에서 문자열을 자주 추가하고 삭제해야 하는데, String 객체를 사용할 경우 매번 새로운 문자열 객체가 생성되어 비효율적입니다.
  • 메모리 사용:
    • StringBuilder는 동일한 메모리 공간을 재사용하므로 메모리 낭비를 줄입니다.

generateCombinations 메서드 상세 분석

private static void generateCombinations(char[] characters, int L, int start, StringBuilder currentCombination) {
    // 현재 조합의 길이가 목표 길이(L)에 도달했을 때
    if (currentCombination.length() == L) {
        if (isValid(currentCombination)) { // 유효한 조합인지 확인
            System.out.println(currentCombination); // 유효하면 출력
        }
        return; // 종료
    }

    // 시작 인덱스부터 남은 문자들을 순차적으로 추가
    for (int i = start; i < characters.length; i++) {
        currentCombination.append(characters[i]); // 문자를 현재 조합에 추가
        generateCombinations(characters, L, i + 1, currentCombination); // 다음 문자 추가를 위해 재귀 호출
        currentCombination.deleteCharAt(currentCombination.length() - 1); // 마지막 문자 제거 (백트래킹)
    }
}

코드 분석

1. 기저 조건 확인:

    if (currentCombination.length() == L) {
    if (isValid(currentCombination)) { // 유효한 조합인지 확인
        System.out.println(currentCombination); // 유효하면 출력
    }
    return; // 종료
    }
  • 현재 조합의 길이가 목표 길이 L에 도달하면, 조합이 유효한지 확인합니다.
  • 유효한 경우 출력하고, 메서드를 종료합니다.

2. 재귀 호출 및 백트래킹:

    for (int i = start; i < characters.length; i++) {
    currentCombination.append(characters[i]); // 문자를 현재 조합에 추가
    generateCombinations(characters, L, i + 1, currentCombination); // 다음 문자 추가를 위해 재귀 호출
    currentCombination.deleteCharAt(currentCombination.length() - 1); // 마지막 문자 제거 (백트래킹)
    }
  • start 인덱스부터 문자를 순차적으로 조합에 추가합니다.
  • 문자를 추가한 후, 재귀 호출을 통해 다음 문자를 추가합니다.
  • 재귀 호출이 끝나면, 마지막에 추가한 문자를 제거하여 이전 상태로 되돌립니다(백트래킹).

isValid 메서드 상세 분석

private static boolean isValid(StringBuilder password) {
    int numVowels = 0;  // 모음 개수
    int numConsonants = 0;  // 자음 개수

    // 조합의 각 문자에 대해 모음인지 자음인지 확인
    for (int i = 0; i < password.length(); i++) {
        char ch = password.charAt(i);
        if (vowels.contains(ch)) { // 모음일 경우
            numVowels++;
        } else { // 자음일 경우
            numConsonants++;
        }
    }

    // 모음이 최소 1개 이상, 자음이 최소 2개 이상이어야 유효한 암호
    return numVowels >= 1 && numConsonants >= 2;
}

코드 분석

모음과 자음 개수 세기:

   int numVowels = 0;  // 모음 개수
   int numConsonants = 0;  // 자음 개수

   for (int i = 0; i < password.length(); i++) {
       char ch = password.charAt(i);
       if (vowels.contains(ch)) { // 모음일 경우
           numVowels++;
       } else { // 자음일 경우
           numConsonants++;
       }
   }
  • numVowels와 numConsonants 변수로 모음과 자음의 개수를 셉니다.
  • 조합의 각 문자를 확인하여, 모음이면 numVowels를 증가시키고, 자음이면 numConsonants를 증가시킵니다.

유효성 조건 확인:

   return numVowels >= 1 && numConsonants >= 2;
  • 모음이 최소 1개 이상, 자음이 최소 2개 이상이어야 유효한 암호로 간주합니다.
  • 위 조건을 만족하면 true를 반환하고, 그렇지 않으면 false를 반환합니다.
저작자표시