[알고리즘] 백준 1759 암호 만들기 -브루트포스, 백트랙킹- 자바 코틀린

www.acmicpc.net/problem/1759

1759번: 암호 만들기

 

 

브루트포스 분류별 풀기에 있는  백준 1759 암호 만들기를 풀어봤습니다. ㅎㅎ

정렬순 + 모음1개 이상 자음 2개이상인지 체크 해서 완전탐색하여 풀었습니다.

브루트포스 분류라 비효울적이여도 통과한 것 같습니다.

 

 

풀이는 다음과 같습니다.

[Java]

import java.util.Arrays;
import java.util.Scanner;

class Main {
    private static String[] arr;
    private static String[] nums;
    private static boolean[] isVisited;
    private static int L;
    private static int C;
    private static StringBuilder sb = new StringBuilder();

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        L = sc.nextInt(); //조합길이
        C = sc.nextInt(); //알파벳총개수(중복없음)
        arr = new String[C];
        nums = new String[L];
        isVisited = new boolean[C];
        for (int i = 0; i < C; i++) {
            arr[i] = sc.next();
        }
        Arrays.sort(arr);
        dfs(0);
        System.out.println(sb.toString());
    }

    private static void dfs(int count) {
        if (count == L) {
            if (!check(nums)) {
                return;
            }
            for (int i = 0; i < L; i++) {
                sb.append(nums[i]);
            }
            sb.append("\n");
            return;
        }
        for (int i = 0; i < C; i++) {
            if (count == 0) {
                isVisited[i] = true;
                nums[count] = arr[i];
                dfs(count+1);
                isVisited[i] = false;
            } else if (!isVisited[i]) {
                if (nums[count - 1].compareTo(arr[i]) < 0) {
                    isVisited[i] = true;
                    nums[count] = arr[i];
                    dfs(count+1);
                    isVisited[i] = false;
                }
            }
        }
    }

    private static boolean check(String[] str) {
        int moeumCnt = 0;
        int jaeumCnt = 0;
        for (String s : str) {
            if (isMoeum(s)) {
                moeumCnt++;
            } else {
                jaeumCnt++;
            }
        }
        return moeumCnt >= 1 && jaeumCnt >= 2;
    }

    private static boolean isMoeum(String s) {
        return s.equals("a") || s.equals("e") || s.equals("i") || s.equals("o") || s.equals("u");
    }

}

 

[Kotlin]

import java.util.*

private lateinit var arr: Array<String?>
private lateinit var nums: Array<String?>
private lateinit var isVisited: BooleanArray
private var L = 0
private var C = 0
private val sb = StringBuilder()


fun main(args: Array<String>) {
    val sc = Scanner(System.`in`)
    L = sc.nextInt() //조합길이
    C = sc.nextInt() //알파벳총개수(중복없음)
    arr = arrayOfNulls(C)
    nums = arrayOfNulls(L)
    isVisited = BooleanArray(C)
    for (i in 0 until C) {
        arr[i] = sc.next()
    }
    Arrays.sort(arr)
    dfs(0)
    println(sb.toString())
}

private fun dfs(count: Int) {
    if (count == L) {
        if (!check(nums)) {
            return
        }
        for (i in 0 until L) {
            sb.append(nums[i])
        }
        sb.append("\n")
        return
    }
    for (i in 0 until C) {
        if (count == 0) {
            isVisited[i] = true
            nums[count] = arr[i]
            dfs(count + 1)
            isVisited[i] = false
        } else if (!isVisited[i]) {
            if (nums[count - 1]!! < arr[i]!!) {
                isVisited[i] = true
                nums[count] = arr[i]
                dfs(count + 1)
                isVisited[i] = false
            }
        }
    }
}

private fun check(str: Array<String?>): Boolean {
    var moeumCnt = 0
    var jaeumCnt = 0
    for (s in str) {
        if (isMoeum(s)) {
            moeumCnt++
        } else {
            jaeumCnt++
        }
    }
    return moeumCnt >= 1 && jaeumCnt >= 2
}

private fun isMoeum(s: String?): Boolean {
    return s == "a" || s == "e" || s == "i" || s == "o" || s == "u"
}

 

 

댓글과 공감은 큰 힘이 됩니다. 감사합니다 !!