[Java, Python] 1759. 암호 만들기

문제

바로 어제 최백준 조교가 방 열쇠를 주머니에 넣은 채 깜빡하고 서울로 가 버리는 황당한 상황에 직면한 조교들은, 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

 

 

🦄 나의 풀이

from copy import deepcopy
L, C=map(int, input().split())  # 암호의 길이, 후보 문자의 종류 개수
alphabet=input().split()
alphabet.sort()
answer=list()

def check(lst) :
    vowel=0
    consonant=0
    for string in lst :
        if string in {'a', 'e', 'i', 'o', 'u'} :
            vowel += 1
        else :
            consonant += 1
    return True if vowel > 0 and consonant > 1 else False

def dfs(start, tmp) :
    if len(tmp) == L :
        if check(tmp) :    # 최소 모음 1개, 자음 2개
            copied_tmp=deepcopy(tmp)
            answer.append(copied_tmp)
        return
    for idx in range(start, C) :
        if alphabet[idx] not in tmp :
            tmp.append(alphabet[idx])
            dfs(idx+1, tmp)
            tmp.pop()

dfs(0, [])
for ans in answer :
    print(''.join(ans))

dfs의 start 파라미터는 시작 인덱스다.

정렬된 암호문을 얻기 위해서 사용함.

 

 

# 실패
from copy import deepcopy
L, C=map(int, input().split())  # 암호의 길이, 후보 문자의 종류 개수
alphabet=input().split()
alphabet.sort()
answer=list()

def check(lst) :
    vowel=0
    consonant=0
    for string in lst :
        if string in {'a', 'e', 'i', 'o', 'u'} :
            vowel += 1
        else :
            consonant += 1
    return True if vowel > 0 and consonant > 1 else False

def dfs(tmp) :
    if len(tmp) == L :
        if check(tmp) :    # 최소 모음 1개, 자음 2개
            if sorted(tmp) not in answer :
                copied_tmp=deepcopy(tmp)
                answer.append(copied_tmp)
            return
    for idx in range(C) :
        if alphabet[idx] not in tmp :
            tmp.append(alphabet[idx])
            dfs(tmp)
            tmp.pop()

dfs([])
for ans in answer :
    print(''.join(ans))

시간초과

백트래킹

 

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

class Main {
    static int L;   // 암호의 길이
    static int C;   // 주어지는 입력 길이
    static BufferedWriter bw;
    static boolean[] visited;
    static String[] str;
    static String s="aeiou";

    public static void main(String[] args) throws IOException{
        BufferedReader br=new BufferedReader(new InputStreamReader(System.in));
        bw=new BufferedWriter(new OutputStreamWriter(System.out));
        String[] num=br.readLine().split(" ");
        L=Integer.parseInt(num[0]);
        C=Integer.parseInt(num[1]);
        visited=new boolean[C];
        str=br.readLine().split(" ");
        Arrays.sort(str);       // 오름차순 정렬

        find(0, 0);
        bw.flush();
    }

    public static boolean check(){
        int cnt_m=0;
        int cnt_j=0;
        for(int i=0; i<C; i++){
            if(visited[i])      // true인 것만
                if(s.contains(str[i])){
                    cnt_m+=1;
            }else{
                    cnt_j+=1;
                }
        }
        if(cnt_m >= 1 && cnt_j >= 2) return true;
        return false;   
    }
    
    public static void find(int start, int depth) throws IOException{
        if(depth == L){
            if(check()){
                for(int i=0; i<C; i++){
                    if(visited[i]) bw.write(str[i]);    
                }
            }else return;
            bw.write("\n");
        }

        for(int i=start; i<C; i++){
            visited[i]=true;
            find(i+1, depth+1);
            visited[i]=false;
        }
    }
}

백트래킹으로 구현

입력값이 정렬되어 있다는 말이 없어서 정렬해주었다.

check 메소드는 자음과 모음의 빈도를 각각 세서 true 또는 false를 반환한다.

check 메소드가 반환한 값이 true여야 버퍼에 기록한다.

 

 

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

class Main {
    static boolean[] isSelected;
    static String[] alphabets;
    static String[] cryptos;
    static int L, C;
    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());

        isSelected=new boolean[C];
        alphabets=new String[C];
        cryptos=new String[L];

        StringTokenizer st1=new StringTokenizer(br.readLine());
        for(int i=0; i<C; i++) alphabets[i]=st1.nextToken();
        Arrays.sort(alphabets);
        comb(0, 0);
        sb.deleteCharAt(sb.length()-1);     
        System.out.print(sb);
    }

    // 모음은 최소 1개 이상, 자음은 최소 2개 이상이면 sb에 추가
    static void comb(int cnt, int target){
        if(cnt == L){
            int aeiouCount=0;   // 모음
            int other=0;        // 자음
            for(String c : cryptos){
                if(c.equals("a") || c.equals("e") || c.equals("i") || c.equals("o") || c.equals("u")) aeiouCount++;
                else other++;
            }
            if(aeiouCount >= 1 && other >= 2){
                for(String c : cryptos){
                    sb.append(c);
                }
                sb.append("\n");
            }
            return;
        }

        for(int i=target; i<C; i++){    // target
            if(isSelected[i]) continue;
            isSelected[i]=true;
            cryptos[cnt]=alphabets[i];
            comb(cnt+1, i+1);
            isSelected[i]=false;
        }
    }
}

다른 사람 풀이를 보고 일부를 고쳤다.

char[]를 String[]로 바꾸고, StringTokenizer로 입력값을 공백으로 나눠서 배열에 담았다.

 

 

🐕 다른 사람 풀이

 

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

class Main {
    static boolean[] isSelected;
    static char[] alphabets;    
    static char[] cryptos;
    static int L, C;
    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());

        isSelected=new boolean[C];
        alphabets=new char[C];
        cryptos=new char[L];

        String line=br.readLine();
        for(int i=0; i<C*2; i+=2){
            alphabets[i/2]=line.charAt(i);  
        }
        Arrays.sort(alphabets);
        comb(0, 0);
        sb.deleteCharAt(sb.length()-1);     // 마지막에 "\n" 제거
        System.out.print(sb);
    }

    // 모음은 최소 1개 이상, 자음은 최소 2개 이상이면 sb에 추가
    static void comb(int cnt, int target){
        if(cnt == L){
            int aeiouCount=0;   // 모음
            int other=0;        // 자음
            for(char c : cryptos){
                if(c=='a' || c=='e' || c=='i' || c=='o' || c=='u') aeiouCount++;
                else other++;
            }
            if(aeiouCount >= 1 && other >= 2){
                for(char c : cryptos){
                    sb.append(c);
                }
                sb.append("\n");
            }
            return;
        }

        for(int i=target; i<C; i++){    // target
            if(isSelected[i]) continue;
            isSelected[i]=true;
            cryptos[cnt]=alphabets[i];
            comb(cnt+1, i+1);
            isSelected[i]=false;
        }
    }
}

StringTokenizer는 구분자로 문자열을 나누는 클래스다.

나는 split(" ")를 주로 썼었는데 새로운 클래스를 알게되었다.🙂

char 배열 alphabets에 입력값을 넣을 때 왜 StringTokenizer를 안 썼지?!라고 생각했었다.

alphabets 배열의 값이 char인데 String을 입력받으면 타입이 안 맞기 때문이다.

 

 

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

class Main {
    static int n, m;
    static String[] numbers;
    static String[] arr;
    static boolean isSelected[];
    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(), " ");

        m=Integer.parseInt(st.nextToken());
        n=Integer.parseInt(st.nextToken());
        numbers=new String[m];

        arr=br.readLine().split(" ");
        Arrays.sort(arr);

        combination(0, 0, 0, 0);
        System.out.print(sb);
    }

    private static void combination(int cnt, int start, int mo_cnt, int ja_cnt){
        if(cnt == m){
            if(1 <= mo_cnt && ja_cnt >= 2){
                String[] tmp=Arrays.copyOf(numbers, m);
                for(int i=0; i<m; i++){
                    sb.append(tmp[i]);
                }
                sb.append("\n");
            }
        return;
        }

        for(int i=start; i<n; i++){
            numbers[cnt]=arr[i];
            if(arr[i].equals("a") ||
                arr[i].equals("o") ||
                arr[i].equals("i") ||
                arr[i].equals("u") ||
                arr[i].equals("e")) combination(cnt+1, i+1, mo_cnt+1, ja_cnt);
            else combination(cnt+1, i+1, mo_cnt, ja_cnt+1);
        }
    }
}

combination 메소드에서 재귀호출, 자음과 모음의 갯수 세기 두 가지 기능을 모두 한다.

 

 

# https://pacific-ocean.tistory.com/454
import sys
input=sys.stdin.readline
def dfs(len, idx) :
    if len == l :
        vo=0
        co=0
        for i in range(l) :
            if arr[i] in 'aeiou' : vo += 1
            else : co += 1
        if vo >= 1 and co >= 2 :
            print(''.join(arr))
        return
    for i in range(idx, c) :
        if check[i] == 0 :
            arr.append(s[i])
            check[i]=1
            dfs(len+1, i+1)
            check[i]=0
            del arr[-1]

l, c=map(int, input().split())
check=[0 for i in range(c)]
arr=[]
s=input().split()
s.sort()
dfs(0, 0)

백트래킹

시작점 idx부터 시작해야 정렬된 암호문을 얻는다.

 

 

문제 출처 👉 백준