[백준/골드5] 1759번 - 암호 만들기 (Java/자바)

1759번: 암호 만들기

암호만들기

시간 제한	메모리 제한	제출	정답	맞힌 사람	정답 비율
2 초	128 MB	48181	22647	15700	44.602%

 

 

문제

 

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

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

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

 

입력

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

 

출력

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

 

예제 입력 및 출력

예제 입력	예제 출력
4 6 a t c i s w	acis acit aciw acst acsw actw aist aisw aitw astw cist cisw citw istw

 

---

문제 접근 방법

 

백트래킹을 이용하여 조합을 구현하고 사용하여 풀었다.

 

Combination 메소드를 만들어 백트래킹을 이용하여 조합을 구현하였는데,

 

문자 하나하나 방문했는지 체크하고(visited[v] = true)

최종적으로 문자열 배열에서 빼내고 싶은 갯수만큼 방문하면 방문한 노드를 print(printCombination)한다음,

마지막으로 방문한 문자를 미방문 상태로 만들어 버렸다(visited[v] = false)

 

해당 문제에는 모음(vowel) 1개, 자음(consonant) 2개 이상이라는 특수 조건이 붙어 있었기 때문에,

해당 문자가 모음인지 확인하는 메소드(isVowel)을 하나 만들어

위의 문자 방문체크시 자음 모음인지 판단하여 갯수를 함께 카운트(countVowel++, countConsonant++)해주고,

특정 문자를 미방문 상태로 만들때 자음/모음의 갯수를 하나씩 없애주었다((countVowel--, countConsonant--)

 

자세한 내용은 아래의 코드를 참고하자

 

이해 안되는 부분이 있거나 설명이 잘못된 부분이 있다면 언제든 댓글을 남겨주세요!

 

---

소스코드

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

public class Main{

    static int L,C;
    static char[] arr;
    static char[] vowel={'a','e','i','o','u'};
    static int countVowel = 0, countConsonant = 0;
    static boolean[] visited;
    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());
        arr = new char[C];
        visited = new boolean[C];

        st = new StringTokenizer(br.readLine());

        for(int i =0; i<C;i++){
            arr[i] = st.nextToken().charAt(0);
        }
        Arrays.sort(arr);
        combination(0,L);
    }

    static void combination(int start,int length){
        if(length == 0){
            printCombination(arr,visited,C);
            return;
        }

        for(int i =start; i<C;i++){
            if(isVowel(arr[i])) countVowel++;
            else countConsonant++;
            visited[i] = true;

            combination(i+1,length-1);

            if(isVowel(arr[i])) countVowel--;
            else countConsonant--;
            visited[i] = false;
        }
    }
    static boolean isVowel(char c){
        for(int i =0; i<vowel.length;i++){
            if(c == vowel[i]) return true;
        }
        return false;
    }
    static void printCombination(char[] arr, boolean[] visited, int n) {
        if(countVowel == 0 || countConsonant<2){
            return;
        }
        for (int i = 0; i < n; i++) {
            if (visited[i]) {
                System.out.print(arr[i]);
            }
        }
        System.out.println();
    }
}