[ 알고리즘 / Kotlin ] 백준 1759 암호 만들기

 

안녕하세요 gyub(귭)입니다 ㅎㅎㅎ

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

1759번: 암호 만들기

 

백준 1759번 암호 만들기 문제입니다!

 

이 문제는 백트래킹으로 풀면 비교적 쉬운 난이도의 문제입니다

 

신경써야할 부분은 두가지 인거 같습니다!!

 

1. 사전순으로 출력

-> 백트래킹을 돌리기전에 정렬해준다

 

2. 최소 한 개의 모음, 최소 두 개의 자음으로 구성

-> 즉, 모음이 한 개 이상이 있음과 동시에 자음이 두 개 이상이 있어야 한다는 말입니다.

 

그러면 코드로 넘어가보겠습니다.

 

fun backTracking(count: Int, start: Int) {
    if (count == l) {
        if (isAnswer(arrP)) {
            for (i in arrP) {
                print("$i")
            }
            println()
        }
        return
    }
    for (i in start until arr.size) {

        if (!vis[arr[i].toInt()]) {
            vis[arr[i].toInt()] = true
            arrP[count] = arr[i]
            backTracking(count + 1, i)
            vis[arr[i].toInt()] = false
        }
    }

백트래킹을 공부하신 분이라면 굳이 설명이 없어도 이해하실꺼 같으니 별다른 설명은 안 하겠습니다!

( 모르신다면 백트래킹 공부부터 먼저 하심이,,, ㅎ)

하지만 BUT!!!! 여기서 isAnswer(arrP)가 중요합니다.

isAnswer메소드는 모음이 한 개 이상이고 자음이 두 개 이상인지 체크하는 메소드 입니당

 

// 모음 한개이상 자음 두개 이상이 들어있는지 체크
private fun isAnswer(arrP: Array<Char>): Boolean {

    val v = listOf('a', 'e', 'i', 'o', 'u')
    var answer = false
    var tmp = 0
    for (i in arrP) {
        if (v.contains(i)) tmp++
    }
    if (tmp >= 1 && tmp <= l - 2) answer = true

    return answer
}

tmp 는 모음의 개수입니다.

if (tmp >= 1 && tmp <= l - 2) answer = true

이쪽이 궁금하실 수 있는데!!

모음의 개수는 한 개 이상이여야 하므로 tmp>=1 이라는 조건이 있고

동시에 자음의 개수는 두 개 이상이여야 하므로 tmp<=l-2 이라는 조건이 붙습니다.

tmp<= l - 2에 대해 설명을 드리면

l은 문제에서 주어진 l 즉, 출력되어질 암호의 개수 입니다.

이 암호의 개수에서 자음의 최소 개수인 2를 뺀 값이 모음의 개수보다 크거나 같아야 한다는 뜻이져~

좀 더 직관적으로 말하면 모음의 개수가 자음의 최소 개수를 침범하지 않을 정도로만 커야 된다는 뜻입니다.

예를 들면

a b c d

a e i d

a b e d

이 세개를 보겠습니다

1. a b c d 

tmp = 1

lc-2 = 4 - 2 =2 이므로 TRUE

 

2. a e i d

tmp = 3

lc-2 = 4-2 = 2 이므로 FALSE

 

3. a b e d

tmp = 2

lc - 2 = 4-2 = 2 이므로 TRUE

 

전체 코드는 깃허브에 있슴다!

 

 

 

봐주셔서 감사합니다!
질문이나 수정되어야 할 부분이 있다면 댓글로 남겨주세요!