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

문제 링크

https://www.acmicpc.net/problem/1759

1759번: 암호 만들기

 

문제 요약

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

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

 

입력

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

 

출력

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

 

접근법

L과 C가 최대 15의 작은 숫자이고, 제한 시간이 2초인 것으로 봤을 때

다른 복잡한 알고리즘을 적용할 필요 없이 브루트포스로 전부 탐색하면서 조건에 맞는 암호 찾을 때마다 출력하는 방식으로 접근했다.

 

단 사전순으로 출력해야하므로

입력받은 알파벳들을 배열에 저장한 뒤 정렬을 하고, 인덱스 순으로 배열을 탐색하며 브루트포싱을 함으로써

자연스럽게 사전순으로 암호가 출력되는 식으로 접근했다.

말이 어렵지 그냥 알파벳들을 저장할 떄 정렬만 한 번 해주고 재귀함수 돌리면 알아서 이렇게 된다.

 

또 브루트포스 문제다 보니 최적화가 필요할지도 모른다고 생각해서

배열을 탐색하며 재귀함수를 돌 때, 남은 후보 알파벳의 개수 + 현재까지 암호에 추가해 둔 알파벳의 수를 더해도 주어진 암호의 길이보다 작을 경우에는 더이상 재귀를 돌아도 암호를 만들어내는 것이 아예 불가능하므로 함수를 종료해버렸다.

 

또 하나 자잘한 최적화는

알파벳을 하나씩 추가하며 암호가 전부 완성되었을 때(길이를 충족했을 때)

암호를 한글자씩 확인하며 자음과 모음의 개수를 세서 조건을 만족하는지 보는 것이 아니라

알파벳을 하나씩 추가할 때 미리미리 자음과 모음의 개수를 세두고

암호가 전부 완성되었을 때 세둔 개수로 조건을 만족하는지만 확인하는 방식을 적용했다.

 

 

시간 복잡도

암호의 배열이 사전순서로 고정되어 있으므로

C개의 문자에서 L개의 문자를 중복 없이, 순서 상관 없이 선택하는 경우의 수만큼 재귀 함수를 수행한다.

기타 자잘한 최적화 때문에 정확히는 이거보단 적게 재귀 함수를 돌긴 한다.

 

 

공간 복잡도

알파벳과 패스워드를 저장하고, 기타 재귀 함수를 돌면서 필요한 변수를 저장할 정도의 메모리만 있으면 되므로

(L + C) * 2 byte에 기타 등등 정도의 메모리만 있으면 된다.

사실상 메모리는 거의 필요하지 않다.

 

 

풀면서 놓쳤던 점

최적화를 한답시고 몇가지 조건을 추가했는데, 문제 자체가 단순한 브루트포스 문제이다 보니 다른 사람들과 크게 차이가 나지 않았다.

오히려 최적화 한다고 수행하는 기타 동작들의 오버헤드가 좀 있었는지 거의 동일한 수준의 실행 시간을 보였다.

브루트포스 문제로 보이면 (특히 코딩테스트 중에서는), 최적화는 일단 신경 쓰지 않고 먼저 문제를 풀어 본다음

그 후에 최적화를 해보는 방식으로 접근을 해야겠다.

 

 

이 문제에서 얻어갈 점

브루트포스 문제 접근 방법

 

 

코드

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

public class Main
{
    //a, e, i, o, u에 해당하는 index의 값이 true인 배열
    static boolean[] isVowelArray;

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

        int pwLen, numOfChars;
        st = new StringTokenizer(br.readLine());
        pwLen = Integer.parseInt(st.nextToken());
        numOfChars = Integer.parseInt(st.nextToken());

        //암호에 들어갈 수 있는 알파벳 후보를 저장해 두는 배열
        char[] charCandidates = new char[numOfChars];

        st = new StringTokenizer(br.readLine());
        for (int i = 0; i < numOfChars; i++)
        {
            char charCandidate = st.nextToken().charAt(0);
            charCandidates[i] = charCandidate;
        }

        //출력을 사전순으로 해야 하기 때문에 알파벳을 미리 사전순으로 정렬해두고
        //오름차순으로 배열을 탐색함
        Arrays.sort(charCandidates);

        //a, e, i, o, u에 해당하는 index의 값을 true로 초기화
        setIsVowelArray();

        printAllPasswordCandidates(new PasswordInfo(pwLen), charCandidates, 0, bw);

        br.close();
        bw.flush();
        bw.close();
    }

    static void printAllPasswordCandidates
            (PasswordInfo pwInfo, char[] charCandidates, int charCandIdx, BufferedWriter bw) throws IOException
    {
        //패스워드가 완성된 경우 (주어진 길이만큼 알파벳을 채워 넣은 경우)
        if (pwInfo.isFullPassword())
        {
            //모음이 1개 이상이고 자음이 2개 이상인 경우에만 출력
            if (pwInfo.isProperPassword())
                bw.write(pwInfo.passwordToString() + "\n");
            return;
        }

        //사전 순서(정렬해 두었으므로 i가 커지는 순서)로 알파벳 배열 탐색하며 password에 알파벳 추가
        for (int i = charCandIdx; i < charCandidates.length; i++)
        {
            //남은 후보 알파벳을 전부 password에 추가해도 password의 길이 조건을 만족하지 못하면
            //추가로 탐색할 필요가 없으므로 종료
            int remainCharCandNum = charCandidates.length - i;
            if (remainCharCandNum + pwInfo.getLength() < pwInfo.getMaxLength())
                return;

            pwInfo.password.add(charCandidates[i]);

            if (isVowel(charCandidates[i]))
            {
                pwInfo.vowelCnt++;
                printAllPasswordCandidates(pwInfo, charCandidates, i + 1, bw);
                pwInfo.vowelCnt--;
            }
            else
            {
                pwInfo.consCnt++;
                printAllPasswordCandidates(pwInfo, charCandidates, i + 1, bw);
                pwInfo.consCnt--;
            }

            pwInfo.removeLastChar();
        }
    }

    //a, e, i, o, u에 해당하는 index의 값을 true로 초기화
    static void setIsVowelArray()
    {
        isVowelArray = new boolean[26];

        isVowelArray['a' - 'a'] = true;
        isVowelArray['e' - 'a'] = true;
        isVowelArray['i' - 'a'] = true;
        isVowelArray['o' - 'a'] = true;
        isVowelArray['u' - 'a'] = true;
    }

    static boolean isVowel(char c)
    {
        return isVowelArray[c - 'a'];
    }
}

class PasswordInfo
{
    ArrayList<Character> password;
    int maxLen;
    int consCnt;
    int vowelCnt;

    PasswordInfo(int maxLen)
    {
        this.maxLen = maxLen;
        this.consCnt = 0;
        this.vowelCnt = 0;
        this.password = new ArrayList<>(maxLen);
    }

    boolean isFullPassword()
    {
        return password.size() == maxLen;
    }

    boolean isProperPassword()
    {
        return consCnt >= 2 && vowelCnt >= 1;
    }

    String passwordToString()
    {
        StringBuilder sb = new StringBuilder();
        for (char c : password)
            sb.append(c);
        return sb.toString();
    }

    void removeLastChar()
    {
        password.remove(password.size() - 1);
    }

    int getLength()
    {
        return password.size();
    }

    int getMaxLength()
    {
        return maxLen;
    }
}