백준 17480 개구쟁이 준석이 Kotlin (이분 탐색)

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

17480번: 개구쟁이 준석이

문제

초등학생 준석이는 영어를 배우고 있는 중이다.

개구쟁이인 준석이는 단어에서 본인이 마음에 드는 부분을 뽑아 섞어 읽고, 뽑은 부분의 알파벳 종류와 개수만 이야기한다.

준석이와 소통하고 싶어하는 진우 선생님은 준석이가 일정한 규칙을 가지고 읽는다는 것을 깨달았다.

진우 선생님이 발견한 규칙은 다음과 같다.

먼저, 준석이는 주어진 단어에서 본인이 읽고 싶은 연속된 문자열을 뽑아 다음의 규칙에 따라 새 문자열을 만든다.

1. 문자열을 반으로 나눈다. 
2. 1번 과정에서 나눠진 두 개의 문자열 중 한 쪽 문자열만 역순으로 바꾼다. 
3. 2번 과정에서 역순으로 바꾸지 않은 다른 한 쪽의 문자열을 다시 반으로 나눈다.
4. 3번 과정에서 반으로 나눈 두 개의 문자열 중 한 쪽 문자열만 역순으로 바꾼다.
5. 1 ~ 4번 과정을 반복한다.  단, 반복하는 과정에서 역순으로 바꿀 문자열은 무작위로 선택하고 선택한 문자열의 길이가 1이라면 역순으로 바꾸지 않고 끝낸다.

위의 규칙에 따라 여러 문자열들을 만들 수 있는데 만약 만들어진 문자열이 중복되면, 오직 1개만 가능한 문자열로 생각한다.

또한 반으로 나눌 문자열 S의 길이가 N이라 하면, N이 홀수일 경우 반으로 나누는 방법은 두 가지가 생긴다.

이 경우, 두 가지를 모두 가능한 방법으로 생각하며 두 가지 방법에서 발생하는 모든 경우의 수도 포함해야 한다.

이런 규칙에 따라 새 문자열을 만들고 나면 준석이는 그 문자열에 포함된 알파벳과 알파벳의 개수를 말한다. (단, 준석이가 잘못 말할 가능성은 없다.)

예를 들어, inconvenience라는 단어가 주어졌다고 하자.

준석이는 e가 2개, n이 2개, i가 1개, c가 1개라고 말한다.

준석이가 말한 조건에 따르면, 준석이가 단어 속에서 뽑은 연속된 문자열은 두 개가 될 수 있다.(enienc, nience)

예시를 위해 enienc를 봤다고 가정하자.

1. enienc를 반으로 나누면 eni와 enc가 된다.
2. eni 또는 enc를 역순으로 바꾼다. 예시에서는 enc의 순서를 역순으로 한다. (cne)
3. eni를 역순으로 바꾸지 않았으므로 eni를 반으로 나눈다. 다만, 정확히 반으로 나눌 수 없기 때문에 e ni와 en i로 두 가지 경우가 생길 수 있다. 예시에서는 e ni일 경우를 설명하겠다.
4. 만약 e를 선택한다면 eni가 되고, ni를 선택한다면 ein이 된다. 따라서, enicne 혹은 eincne가 된다.

이처럼 inconvenience라는 단어가 주어지고, 준석이가 단어 속에서 뽑은 연속된 문자열 enienc과 nience에 대하여 

준석이의 규칙에 의해 만들어진 문자열들은 eincne, einnce, einnec, enicne, ineecn, ineenc, inenec, neicne, neiecn, nieecn으로 총 10개다.

진우 선생님은 준석이와 소통을 하기 위해 준석이의 규칙에 의해 만들어질 문자열들을 모두 알아내고자 한다.

진우 선생님을 도와 주어진 단어, 준석이가 말한 알파벳과 알파벳들의 개수를 토대로 규칙에 따라 만들 수 있는 문자열들의 개수를 출력하는 프로그램을 만들자.

입력

첫째 줄에 준석이가 말한 알파벳 종류의 개수가 주어진다. 단, 알파벳 종류의 개수는 N개(0 < N < 15)다.

둘째 줄에는 준석이가 말한 알파벳들과 각각의 개수가 주어진다. 단, 각각의 개수는 M개(0 < M < 15)다.

세번째 줄에는 알파벳 소문자로 이루어진 영어 단어가 주어진다. 단, 영어 단어의 길이는 알파벳 각각의 갯수들의 합 이상이며 15자 미만이다. 

출력

규칙에 따라 만들 수 있는 문자열의 개수를 출력한다. 단, 중복되는 문자열일 경우 그 문자열은 1개로 취급해야 한다. 

알고리즘 분류

• 구현
• 브루트포스 알고리즘
• 재귀

풀이

19년도 중앙대 문제라고 하는데 왜리 푼 사람이 없지

문제도 좋은 것 같다.

풀이의 뎁스가 2 이상인 문제

풀이의 뎁스란.. 답을 구하기 위해 하나의 알고리즘, 풀이를 사용하는 게 아니라 거기에 나아가서 하나 더 사용하는.. 내 멋대로 정한 말이다.

우선 주어진 문자열에서 사용 가능한 문자들로 부분 문자열을 추출한다.

이 부분 문자열은 기존 문자열에서 연속된 경우만 가능하다.

본인은 처음에 연속되지 않아도 되는 줄 알고 combination 짰다 ㅎㅎ

 

이렇게 부분 문자열을 추출하면, 그 부분 문자열을 가지고 이분 탐색을 한다.

이분 탐색은 재귀, 그냥 반복문 두 가지 방법으로 짤 수 있다.

반복문이 더 성능이 좋지만, 이 문제에선 홀수인 경우, 예를 들어 길이가 5인 경우 2/3으로 나누는 경우, 3/2로 나누는 경우 두 가지를 모두 탐색해야 하고, 문자열 변경 성능 최적화를 위해선 부분 문자열을 뒤집었다가 다시 되돌려야 하기 때문에 재귀 함수로 구현했다.

 

binaryDfs라는 함수명은 귀엽게 봐주세유

 

그냥.. 일반적인 binary 함수 보단 백트래킹 느낌이 나서 그랬다. 근데 왜 dfs?

무튼 나머진 그냥 조건에 맞게 이분 탐색 구현이다.

왼쪽 덩어리를 reverse하면 오른쪽 덩어리에 대해 이분 탐색,

오른쪽 덩어리를 reverse하면 왼쪽 덩어리에 대해 이분 탐색,

그리고 mid값에 +1을 하여 다시 위의 두 가지 탐색

reverse는 본인의 취향대로 최적화해서 짜면 된다.

코드

import java.util.*
val br = System.`in`.bufferedReader()
fun getIntList() = br.readLine().split(' ').map { it.toInt() }
fun getInt() = br.readLine().toInt()

/*
* 1.가능한 문자열 추출
* 2.추출한 문자열로 dfs하여 최종 문자열 추출 (중복 불가)
* */
val chArr = IntArray(26)
var len = 0
val resultSet = mutableSetOf<String>()

fun reverse(s: Int, e: Int, word: StringBuilder){
    for(i in s until (s+e)/2){
        word[e-1-(i-s)] = word[i].also{word[i] = word[e-1-(i-s)]}
    }
}

//e는 길이 (마지막 인덱스+1)
fun binaryDfs(s: Int, e: Int, word: StringBuilder){
    if(s>=e-1){
        if(!resultSet.contains(word.toString())){
            resultSet.add(word.toString())
        }
        return
    }
    val len = s+e
    var mid = (len)/2

    //왼쪽 reverse, 오른쪽 반띵
    reverse(s,mid,word)
    binaryDfs(mid,e,word)
    reverse(s,mid,word)

    //오른쪽 reverse, 왼쪽 반띵
    reverse(mid,e,word)
    binaryDfs(s,mid,word)
    reverse(mid,e,word)

    //길이가 홀수인 경우는 나누는 방법이 2가지
    if(len%2!=0){
        mid++
        //왼쪽 reverse, 오른쪽 반띵
        reverse(s,mid,word)
        binaryDfs(mid,e,word)
        reverse(s,mid,word)

        //오른쪽 reverse, 왼쪽 반띵
        reverse(mid,e,word)
        binaryDfs(s,mid,word)
        reverse(mid,e,word)
    }
}

fun canWord(idx: Int, word: String): Boolean {

    val tempChArr = IntArray(26) { chArr[it] }

    for (i in 0 until len) {
        if (tempChArr[word[idx + i] - 'a'] == 0) return false
        tempChArr[word[idx + i] - 'a']--
    }
    return true
}

fun main() = with(System.out.bufferedWriter()) {
    //input
    val n = getInt()
    br.readLine().split(' ').apply {
        for (i in 0 until this.size - 1 step 2) {
            val cnt = Character.getNumericValue(this[i + 1][0])
            chArr[this[i][0] - 'a'] = cnt
            len += cnt
        }
    }
    val word = br.readLine()

    //solve
    //가능한 문자열 추출
    for (i in 0 .. word.length - len) {
        if(canWord(i, word)){
            val subWord = word.substring(i,i+len)
            //가능한 문자열로 최종 문자열 찾기
            binaryDfs(0,subWord.length,StringBuilder(subWord))
        }
    }
    //output
    write("${resultSet.size}")
    close()
}