[백준] 암호 만들기

문제 주소

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

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

제출 코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.*;

public class Main {
    static char [] letter;

    public static void main(String[] args) throws IOException {

        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        StringTokenizer st = new StringTokenizer(br.readLine());
        int L = Integer.parseInt(st.nextToken());
        int C = Integer.parseInt(st.nextToken());

        letter = new char[C];

        st = new StringTokenizer(br.readLine());
        for(int i=0; i<C; i++){
            char c = st.nextToken().charAt(0);
            letter[i] = c;

        }
        Arrays.sort(letter);

        String s = "";
        search(L,s,-1);

    }

    public static void search(int limit, String s, int max){
        if(limit==s.length()){
            if(check(limit,s)){
                System.out.println(s);
            }
            return;
        }

        for(int i=max+1;i<letter.length;i++){
            String temp = new String(s);

            temp += letter[i];
            search(limit,temp,i);
        }
    }

    public static boolean check(int limit,String s){
        if(s.length()!=limit){
            return false;
        }
        int upper = 0;
        int lower = 0;
        for(int i=0;i<s.length();i++){
            char c = s.charAt(i);
            if(c=='a'||c=='e'||c=='i'||c=='o'||c=='u'){
                lower++;
            }else{
                upper++;
            }
        }
        if(upper>=2&&lower>=1){
            return true;
        }
        return false;
    }
}

 

코드 해설

백트래킹 문제같은 방식으로 풀었다

String을 파라미터로 받아서 letter에 저장된 가능한 char중 안 쓴것만 덧붙여서 재귀함수에 다시 넣음,

이때 max에다가 포함된 글자중에 가장 큰 글자의 인덱스를 저장해서

max+1부터 붙여 사전순으로 덧붙여지게 함

 

풀이과정

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.*;

public class Main {
    static boolean [] visit;
    static char [] letter;

    public static void main(String[] args) throws IOException {

        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        StringTokenizer st = new StringTokenizer(br.readLine());
        int L = Integer.parseInt(st.nextToken());
        int C = Integer.parseInt(st.nextToken());

        letter = new char[C];
        visit = new boolean[C];

        st = new StringTokenizer(br.readLine());
        for(int i=0; i<C; i++){
            char c = st.nextToken().charAt(0);
            letter[i] = c;

        }
        Arrays.sort(letter);

        String s = "";
        search(L,s);

    }

    public static void search(int limit, String s){
        if(limit==s.length()){
            if(check(s)){
                System.out.println(s);
            }
            return;
        }

        Arrays.fill(visit,false);

        for(int i=0;i<s.length();i++){
            char c = s.charAt(i);
            for(int j = 0;j<letter.length;j++){
                if(c==letter[j]){
                    visit[j] = true;
                    break;
                }
            }
        }

        for(int i=0;i<letter.length;i++){
            if(visit[i]){
                continue;
            }
            String temp = new String(s);

            temp += letter[i];
            search(limit,temp);
        }
    }

    public static boolean check(String s){
        int upper = 0;
        int lower = 0;
        for(int i=0;i<s.length();i++){
            char c = s.charAt(i);
            if(c=='a'||c=='e'||c=='i'||c=='o'||c=='u'){
                lower++;
            }else{
                upper++;
            }
        }
        if(upper>=2&&lower>=1){
            return true;
        }
        return false;
    }
}

 

처음에 이렇게 짰는데 그러니까 사전순이 안 지켜지고 사용되지 않은 글자는 순서에 상관 없이 그냥 다 붙어서 나옴

acis
acit
aciw
acsi
acst
acsw
acti
acts
actw
acwi
acws
acwt
aics
aict
aicw
aisc
aist
aisw
aitc
aits
aitw
aiwc
aiws
aiwt
asci
asct
ascw
asic
asit
asiw
astc
asti
astw
aswc
aswi
aswt
atci
atcs
atcw
atic
atis
atiw
atsc
atsi
atsw
atwc
atwi
atws
cais
cait
caiw
casi
cast
casw
cati
cats
catw
cawi
caws
cawt
cias
ciat
ciaw
cisa
cist
cisw
cita
cits
citw
ciwa
ciws
ciwt
csai
csat
csaw
csia
csit
csiw
csta
csti
cswa
cswi
ctai
ctas
ctaw
ctia
ctis
ctiw
ctsa
ctsi
ctwa
ctwi
iacs
iact
iacw
iasc
iast
iasw
iatc
iats
iatw
iawc
iaws
iawt
icas
icat
icaw
icsa
icst
icsw
icta
icts
ictw
icwa
icws
icwt
isac
isat
isaw
isca
isct
iscw
ista
istc
istw
iswa
iswc
iswt
itac
itas
itaw
itca
itcs
itcw
itsa
itsc
itsw
itwa
itwc
itws
saci
sact
sacw
saic
sait
saiw
satc
sati
satw
sawc
sawi
sawt
scai
scat
scaw
scia
scit
sciw
scta
scti
scwa
scwi
siac
siat
siaw
sica
sict
sicw
sita
sitc
sitw
siwa
siwc
siwt
stac
stai
staw
stca
stci
stia
stic
stiw
stwa
stwi

그래서 사전순을 지키기 위해 max 변수를 도입함

int max = -1;
        for(int i=0;i<s.length();i++){
            char c = s.charAt(i);
            for(int j = 0;j<letter.length;j++){
                if(c==letter[j]){
                    visit[j] = true;
                    max = j;
                    //break;
                }
            }
        }

        for(int i=max+1;i<letter.length;i++){
            if(visit[i]){
                continue;
            }
            String temp = new String(s);

            temp += letter[i];
            search(limit,temp);
        }

→

int max = -1;
        for(int i=0;i<s.length();i++){
            char c = s.charAt(i);
            for(int j = 0;j<letter.length;j++){
                if(c==letter[j]){
                    visit[j] = true;
                    max = j;
                    //break;
                }
            }
        }

        for(int i=max+1;i<letter.length;i++){
            if(visit[i]){
                continue;
            }
            String temp = new String(s);

            temp += letter[i];
            search(limit,temp);
        }

max에다가 저장해서 i+1부터 돌아가게 함!

저거 추가해주고 잘 돌아갔다!

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

 

 

제출한 코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.*;

public class Main {
    static boolean [] visit;
    static char [] letter;

    public static void main(String[] args) throws IOException {

        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        StringTokenizer st = new StringTokenizer(br.readLine());
        int L = Integer.parseInt(st.nextToken());
        int C = Integer.parseInt(st.nextToken());

        letter = new char[C];
        visit = new boolean[C];

        st = new StringTokenizer(br.readLine());
        for(int i=0; i<C; i++){
            char c = st.nextToken().charAt(0);
            letter[i] = c;

        }
        Arrays.sort(letter);

        String s = "";
        search(L,s);

    }

    public static void search(int limit, String s){
        if(limit==s.length()){
            if(check(limit,s)){
                System.out.println(s);
            }
            return;
        }

        Arrays.fill(visit,false);

        int max = -1;
        for(int i=0;i<s.length();i++){
            char c = s.charAt(i);
            for(int j = 0;j<letter.length;j++){
                if(c==letter[j]){
                    visit[j] = true;
                    max = j;
                    break;
                }
            }
        }

        for(int i=max+1;i<letter.length;i++){
            if(visit[i]){
                continue;
            }
            String temp = new String(s);

            temp += letter[i];
            search(limit,temp);
        }
    }

    public static boolean check(int limit,String s){
        if(s.length()!=limit){
            return false;
        }
        int upper = 0;
        int lower = 0;
        for(int i=0;i<s.length();i++){
            char c = s.charAt(i);
            if(c=='a'||c=='e'||c=='i'||c=='o'||c=='u'){
                lower++;
            }else{
                upper++;
            }
        }
        if(upper>=2&&lower>=1){
            return true;
        }
        return false;
    }
}

 

근데 생각해보면 max 이후로 어차피 안 넣을 거니까 visit에 체크하는 과정도 필요가 없음

그래서 visit 배열 빼고 max를 파라미터에 추가해줌

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.*;

public class Main {
    static char [] letter;

    public static void main(String[] args) throws IOException {

        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        StringTokenizer st = new StringTokenizer(br.readLine());
        int L = Integer.parseInt(st.nextToken());
        int C = Integer.parseInt(st.nextToken());

        letter = new char[C];

        st = new StringTokenizer(br.readLine());
        for(int i=0; i<C; i++){
            char c = st.nextToken().charAt(0);
            letter[i] = c;

        }
        Arrays.sort(letter);

        String s = "";
        search(L,s,-1);

    }

    public static void search(int limit, String s, int max){
        if(limit==s.length()){
            if(check(limit,s)){
                System.out.println(s);
            }
            return;
        }

        for(int i=max+1;i<letter.length;i++){
            String temp = new String(s);

            temp += letter[i];
            search(limit,temp,i);
        }
    }

    public static boolean check(int limit,String s){
        if(s.length()!=limit){
            return false;
        }
        int upper = 0;
        int lower = 0;
        for(int i=0;i<s.length();i++){
            char c = s.charAt(i);
            if(c=='a'||c=='e'||c=='i'||c=='o'||c=='u'){
                lower++;
            }else{
                upper++;
            }
        }
        if(upper>=2&&lower>=1){
            return true;
        }
        return false;
    }
}

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

잘 돌아간다