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

암호 만들기

풀이

입력으로 들어온 문자를 이용해 주어진 길이에 맞는 문자열을 조합하는 문제이다.

몇 가지 조건만 지키면 간단하게 풀 수 있고, 이전에 풀었던 n과 m 문제와 동일하기 때문에 쉽게 풀이할 수 있었다.

문제의 조건으로는

최소 한 개의 모음과 최소 두 개의 자음을 포함할 것
알파벳이 증가하는 순서로 배열될 것

두 가지이다.

증가하는 순서로 배치하기 위애 먼저 입력으로 들어온 문자들을 아스키 코드 순서대로 정렬을 하고 문자열을 이룰 때 이전의 인덱스의 값을 가져오지 않도록 하면 된다.

그리고 최소 한 개의 모음과 최소 두 개의 자음이 포함되어야 하기때문에 최종적으로 문자열이 만들어졌을 때 조건을 충족하는지 검사를 하고 충족한다면 리스트에 추가한다.

위와 같은 방식으로 코드를 작성하여 풀이했다.

코드

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

public class Main {
    static int[] dx = {0, 0, -1, 1};
    static int[] dy = {1, -1, 0, 0};
    static int ans = 0;
    static int l;
    static boolean[] visit;
    static Set<String> set;
    static String[] consonant = {"b","c","d","f","g","h","j","k","l","m","n","p","q","r","s","t","v","w","x","y","z"};
    static String[] vowel = {"a", "e", "i", "o", "u"};

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        String[] first = br.readLine().split(" ");
        l = Integer.parseInt(first[0]);
        int c = Integer.parseInt(first[1]);
        String[] arr = br.readLine().split(" ");
        Arrays.sort(arr);
        visit = new boolean[c];
        set = new HashSet<>();

        select(arr, "", 0, 0);

        List<String> ansList = new ArrayList<>(set);

        Collections.sort(ansList);
        for (String a : ansList)
            bw.write(a + "\n");
        br.close();
        bw.close();
    }

    private static boolean checkVowel(String result) {
        for (int i = 0; i < 5; i++) {
            if (result.contains(vowel[i]))
                return true;
        }
        return false;
    }

    private static boolean checkConsonant(String result) {
        int cnt = 0;
        for(int i = 0;i< consonant.length;i++){
            if(result.contains(consonant[i])){
                cnt++;
            }
            if(cnt == 2)
                return true;
        }
        return false;
    }

    private static void select(String[] arr, String result, int pos, int cnt) {
        if (cnt == l) {
            if (checkVowel(result) && checkConsonant(result)) {
                //System.out.println("hi " + result);
                set.add(result);
            }
            return;
        }
        for (int i = pos; i < arr.length; i++) {
            if (!visit[i]) {
                result += arr[i];
                visit[i] = true;
                select(arr, result, i, cnt + 1);
                visit[i] = false;
                result = result.substring(0, result.length() - 1);
            }
        }
    }
}