백준 2922 즐거운 단어 Kotlin (백트래킹)

문제 출처 : https://www.acmicpc.net/problem/2922

2922번: 즐거운 단어

문제

상근이는 자신이 다니는 학교에서 영어단어를 가장 많이 외우고 있다. 그 비법은 바로 조기교육이었다. 상근이는 젖병을 물기도 전에 영어 단어를 외웠다. 따라서, 지금은 자리에 앉으면 사전을 만들 수 있을 정도로 많이 외우게 되었다.

더 이상 외울 단어가 없어진 상근이는 이제 단어를 만들기로 결심했다.

상근이는 단어는 두 종류, 즐거운 단어와 즐겁지 않은 단어로 분류할 수 있다고 생각한다. 새로운 단어를 만들기 위해 즐겁지 않은 단어를 공책에 적는다. 그 다음, 보기 싫은 알파벳을 지우개로 지우고 그 자리에 밑 줄(_)을 적는다. 이렇게 보기 싫은 단어를 모두 지운 다음에는 즐거운 단어를 만들 수 있도록 밑 줄에 알파벳을 적는다.

상근이에게 즐거운 단어란, 모음(A,E,I,O,U)이 연속해서 3번, 자음(모음을 제외한 나머지 알파벳)이 연속해서 3번 나오지 않아야 한다. 또, L을 반드시 포함해야 한다.

상근이게 보기 싫은 알파벳을 지운 단어가 주어졌을 때, 즐거운 단어를 만들 수 있는 경우의 수를 세는 프로그램을 작성하시오.

입력

첫째 줄에 상근이가 공책에 적은 단어가 주어진다. 단어의 길이는 최대 100이고, 알파벳 대문자와 밑 줄(_)로만 이루어져 있다. 단어에 포함된 밑 줄의 개수는 최대 10이다.

출력

첫째 줄에, 밑 줄을 알파벳으로 바꿔 즐거운 단어를 만들 수 있는 경우의 수를 출력한다.

힌트

정답은 263-1을 넘지 않는다.

알고리즘 분류

• 브루트포스 알고리즘
• 백트래킹

풀이

우선 조건을 살펴보자.

1. 26개의 알파벳이 _자리에 올 수 있다.

2. 무조건 L이 포함되어야 한다.

3. 모음이 연속 3번, 자음이 연속 3번 이상이면 안 된다.

 

_이 없다고 생각해 보자.

입력 문자열의 길이는 최대 100이므로 최대 100번 탐색하면 답은 1로 끝.

_이 있을 때를 생각해 보자.

우리는 _에 어떤 요소를 넣을지 고민해야 하고, 3가지 분류로 나눌 수 있다.

1. L

2. 모음 (5개)

3. L을 제외한 자음 (20개)

오... 뭘 넣어야지?

우리는 개발자다, 똑똑한 개발자는 이딴 걸 고민하지 않고 죄다 때려 넣고 컴퓨터에게 일을 시킨다.

"돈을 위해 일하지 말고 돈이 나를 위해 일하게 만들어라" - 로버트 기요사키

갑자기 떠올랐다.

무튼 이런 부분에서 우리는 Lazy한 사장 마인드를 가져야 한다.

나의 소중한 일꾼이 파업을 하지 않을 정도로만 일을 넘겨줘야 한다.

_은 최대 10개라고 했다.

10개에 각각 위 3가지 분류를 넣으면 3^10번 넣으면 된다.

??? : 대충 1억 번 이상 들어오면 파업^^

3^10은 대충 6만이다.

6만 개의 값을 넣어주기만 하면 나의 일꾼이 즐거운 단어인지 확인해 준단다.

 

주어진 Input을 0번 인덱스 부터 확인한다.

현재 인덱스의 문자가 밑줄이라면?

1. L을 넣고 다음 인덱스로 넘어간다

2. 모음을 넣고 다음 인덱스로 넘어간다.

3. L 제외 자음을 넣고 다음 인덱스로 넘어간다.

현재 인덱스의 문자가 알파벳이라면?

모음인 경우  모음 카운트 +1, 자음 카운트 초기화하고 다음 인덱스로 넘어간다.

자음인 경우 자음 카운트 +1, 모음 카운트 초기화하고 다음 인덱스로 넘어간다.

 

재귀 함수의 return조건은 모음 혹은 자음이 3번 연속 나온 경우, 문자열을 넘어간 경우이다.

문자열을 넘어간 경우 L이 없다면 꽝, L이 있다면 답을 갱신하면 된다.

 

이번 풀이는 매우 피곤한 상태로 작성하여 풀이보단 그냥 코드를 보는 것을 추천한다.

코드

val br = System.`in`.bufferedReader()
val vowels = setOf<Char>('A', 'E', 'I', 'O', 'U')
var answer = 0L
fun main() = with(System.out.bufferedWriter()) {

    //input
    val input = br.readLine()
    //solve
    backTracking(input.contains('L'), 1, 1, 0, 0, 0, input)
    //output
    write("$answer")
    close()
}

fun backTracking(haveL: Boolean, vowelLine: Long, consonantLine: Long, idx: Int, vowelCnt: Int, consonantCnt: Int, input: String) {
    if (vowelCnt == 3 || consonantCnt == 3) return
    if (idx == input.length) {
        if (!haveL) return
        answer += vowelLine * consonantLine
        return
    }
    val ch = input[idx]
    if (ch == '_') {
        //모음
        backTracking(haveL, vowelLine * 5, consonantLine, idx + 1, vowelCnt + 1, 0, input)
        //L제외 자음
        backTracking(haveL, vowelLine, consonantLine * 20, idx + 1, 0, consonantCnt + 1, input)
        //L
        backTracking(true, vowelLine, consonantLine, idx + 1, 0, consonantCnt + 1, input)
    } else {
        if (vowels.contains(ch)) {//모음인 경우
            backTracking(haveL, vowelLine, consonantLine, idx + 1, vowelCnt + 1, 0, input)
        } else {
            //자음인 경우
            backTracking(haveL, vowelLine, consonantLine, idx + 1, 0, consonantCnt + 1, input)
        }
    }
}