[알고리즘풀이]백준 1759 : 암호 만들기 JAVA

목차

• 개요
•  본문
•  1) 문제
•  2) 과정
•  3) 코드 전체

 

개요

이번 알고리즘 스터디에서 JAVA를 이용해 백준 1759번 암호 만들기 문제를 풀게 되었습니다.

1759번: 암호 만들기

본문

1) 문제

백준 1759번 암호 만들기는 btruteforce입니다.

 

2) 과정

이 문제는 그렇게 어렵게 푼 건 아니였어요. 여러 알고리즘 문제중에 후반에 푼 편이기도 해서 골드 5보단 실버정도에 가까운 문제였어요.

 

코드는 입력, 로직, 출력으로 구분하였습니다.

입력에는 input()이 있고 로직에는 재귀되는 함수인 recFunc, 모음이 있는지 확인하는 containsVow, 자음이 있는지 확인하는 containsCon이 있습니다. 마지막 출력에는 output()으로 구성했습니다.

 

2-1) main

    public static void main(String[] args) throws IOException {
        input();
        recFunc("",0);
        output();
    }

main은 다음과 같습니다. 입력, 로직, 출력을 차례대로 부르는 형태입니다.

 

2-2) input()

    private static void input() throws IOException {
        BufferedReader reader = new BufferedReader(new InputStreamReader(System.in));
        String[] strArrFirst = reader.readLine().split(" ");
        l = Integer.parseInt(strArrFirst[0]);
        c = Integer.parseInt(strArrFirst[1]);

        strArr = reader.readLine().split(" ");
        Arrays.sort(strArr);

        answers = new ArrayList<String>();
    }

BufferedReader를 통해 콘솔로부터 데이터를 받아오게하고, 첫줄에 입력된 값을 가져와 암호 후보의 알파벳 개수인 l과 암호의 알파벳 개수인 c를 저장합니다. 그리고 두번째줄은 알파벳들이기 때문에 이를 strArr로 받아 후에 사용하기 좋게 정렬까지 해줍니다. 그리고 정답을 담을 arrayList인 answers까지 new해주면 input은 끝입니다.

 

2-3) recFunc (String str, int index)

    private static void recFunc(String str, int index){
        if(index==l) answers.add(str);
        for(int i=index;i<strArr.length;i++){
            if(str.equals("") ||(str.substring(str.length()-1).compareTo(strArr[i]))<0){
                recFunc(str+strArr[i],index+1);
            }
        }
    }

파라미터 >> 

recFunc의 두 파라미터는 각각 index를 거쳐오며 저장된 암호후보의 str 값, 재귀함수의 재귀 수준을 나타내는 index 값입니다.

 

if(index==l) answers.add(str); >>

index가 암호의 알파벳 수인 l과 같아지면 암호후보 하나가 완성된 것입니다. 그러니 이를 answers에 저장하고 다음 for문은 들어가지도 않은채 끝이 납니다.

 

for문 >>

str에 아무것도 없거나 차례대로 이미 알파벳을 정렬해두었기에 마지막 글자이후의 값만 가져오게하여 중복을 줄이도록 if문을 걸어줍니다. if문을 통과하면 해당 알파벳을 str에 추가하고 index에 1을 더해 다음 index를 다루도록 넘깁니다.

 

2-4) containsVow, containsCon

    private static boolean containsVow(String answer){
        for(String s:vowelsType) if(answer.contains(s)) return true;
        return false;
    }

    private static boolean containsCon(String answer){
        int cases = 0;
        for(String s:consonantType) if(answer.contains(s)) cases++;
        return cases >= 2;
    }

containsVow와 containsCon은 모음과 자음을 찾아오는 함수입니다. 모음 String을 담은 vowelsType과 자음 String을 담은 consonantType을 돌며 파라미터로 받은 answer(암호 후보)이 조건(vow의 경우 1개이상, con의 경우 2개이상)이 성립하는지 체크해 boolean값을 리턴해줍니다.

 

2-5) output

    private static void output() {
        int k=0;
        for (String answer : answers) {
            if(containsVow(answer) && containsCon(answer)) 
                System.out.println(answer);
        }
    }

output에서는 그간 받은 암호후보들을 담은 answers를 돌며 자음과 모음 조건을 성립하는지 체크해 성립한다면 이를 출력하도록했습니다.

 

 

3) 전체코드

그렇게 완성된 코드는 다음과 같습니다.

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

public class Main {
    private static final String[] vowelsType ={"a","e","i","o","u"};
    private static final String[] consonantType ={"b","c","d","f","g","h","j",
            "k","l","m","n","p","q","r","s","t","v","w","x","y","z"};

    private static int l,c;
    private static String[] strArr;
    private static ArrayList<String> answers;


    private static void input() throws IOException {
        BufferedReader reader = new BufferedReader(new InputStreamReader(System.in));
        String[] strArrFirst = reader.readLine().split(" ");
        l = Integer.parseInt(strArrFirst[0]);
        c = Integer.parseInt(strArrFirst[1]);

        strArr = reader.readLine().split(" ");
        Arrays.sort(strArr);

        answers = new ArrayList<String>();
    }

    private static void recFunc(String str, int index){
        if(index==l) answers.add(str);
        for(int i=index;i<strArr.length;i++){
            if(str.equals("") ||(str.substring(str.length()-1).compareTo(strArr[i]))<0){
                recFunc(str+strArr[i],index+1);
            }
        }
    }

    private static boolean containsVow(String answer){
        for(String s:vowelsType) if(answer.contains(s)) return true;
        return false;
    }

    private static boolean containsCon(String answer){
        int cases = 0;
        for(String s:consonantType) if(answer.contains(s)) cases++;
        return cases >= 2;
    }

    private static void output() {
        int k=0;
        for (String answer : answers) {
            if(containsVow(answer) && containsCon(answer)) 
                System.out.println(answer);
        }
    }

    public static void main(String[] args) throws IOException {
        input();
        recFunc("",0);
        output();
    }

}

깃헙으로 더 자세히 보고싶으시다면, 아래 링크를 참고해주세요 :)

https://github.com/Park1122/Algorithm-Study/blob/master/sujeong/bruteforce/BOJ1759.java

GitHub - Park1122/Algorithm-Study: 명지대학교 학생들이 모여서 만든 알고리즘 공부 및 코딩테스트 준비