백준 13908 비밀번호 Kotlin (순열)

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

13908번: 비밀번호

문제

웅찬이는 근성이 대단한 도둑이다. 그래서 금고를 털 때, 모든 조합을 눌러본다. 예를 들어 비밀번호가 3글자 라는 사실을 알 때, 000, 001, 002, 003, … 998, 999의 모든 조합을 눌러본다. 그러나 웅찬이는 선견지명이 있어서 비밀번호에 어떤 숫자가 들어가는지 일부 알 수 있다. 예를 들어 3글자 비밀번호에 0이 들어감을 안다면 999 와 같이 0이 들어가지 않는 수는 가능성이 없다. 그러나 000, 012, 030과 같은 수는 가능하다. 비밀번호의 길이와 선견지명으로 알게된 비밀번호의 일부 숫자가 주어질 때, 모든 가능한 비밀번호의 개수를 출력하는 프로그램을 작성하시오.

입력

첫줄에 비밀번호의 길이 n (1 ≤ n ≤ 7), 선견지명으로 알게된 비밀번호에 들어가는 수 m(0 ≤ m ≤ n) 이 주어지고, 둘째 줄에 m개의 서로 다른 숫자(0~9)가 주어진다. m이 0인 경우 둘째 줄은 주어지지 않는다.

출력

가능한 모든 비밀번호의 개수를 출력한다.

힌트

첫 번째 예제의 경우 가능한 비밀번호의 조합은 07, 17, 27, 37, 47, 57, 67, 70, 71, 72, 73, 74, 75, 76, 77, 78, 79, 87, 97이다. 두 번째 예제의 경우 가능한 비밀번호의 조합은 34, 43이다.

알고리즘 분류

• 수학
• 브루트포스 알고리즘
• 조합론
• 포함 배제의 원리

풀이

dfs를 사용한 순열 알고리즘으로 풀 수 있다.

순열인 이유는, 100과 001은 다른 비밀번호이기 때문이다.

둘째 줄에 주어진 m개의 서로 다른 수는, 비밀번호의 조합에서 필수로 있어야 하는 수들이다.

따라서 toUse에 Boolean 형태로 m 개의 수를 저장해놓자.

 

이후, dfs 과정에서 한 자릿수에 0부터 9까지의 수를 넣는다고 할 때,

toUse[i]가 true이면(i가 선견지명으로 알게된 수라면) toUse[i]를 사용했다고 false처리하고, 선견지명으로 알게된 수를 사용한 횟수(cnt)를 1개 늘려서 다음 자릿수를 탐색한다.

toUse[i]가 false이면 cnt를 늘리지 않은 채 다음 자릿수를 탐색한다.

 

마지막 자릿수까지 숫자를 채워 넣었다면, cnt==m인지 (선견지명으로 알게 된 수를 모두 사용한 비밀번호인지)를 확인하여 수를 세어준다.

 

핵심 코드 

    for(i in 0 .. 9){
        if(toUse[i]){
            toUse[i]=false
            permutation(len+1, end,m, cnt+1)
            toUse[i]=true
        }
        else{
            permutation(len+1,end,m,cnt)
        }
    }

 

처음엔 선견지명으로 알게 된 수들을 탐색 과정에서 활용하지 않고, 모든 비밀번호 경우의 수를 만들고, 선견지명으로 알게 된 수를 사용했는지 검사했다.

이러면 시간이 오래 걸리지만 통과는 된다.

여기서, 비밀번호의 결과를 ArrayList에 저장한 경우 통과,

비밀번호의 결과를 재귀 함수 내에 String으로 저장하여 메모리 초과가 났다.

처음엔 재귀 함수의 깊이는 문제없는데, 재귀 함수 내부의 데이터 커서, 재귀 함수 내의 String 때문에 스택오버플로우가 발생한 줄 알았다.

그래서 비밀번호의 결과 String을 전역 함수로 빼서 사용했는데도 메모리 초과가 떴다.

그럼 결론은 스택오버플로우가 아니라, 전체 메모리 초과인 듯하다.

왜 String을 사용하면 메모리 초과가 날까?????   

또, 같은 로직의 비밀번호의 결과를 재귀 함수 내부에 string으로 둔 c++코드는 메모리 초과가 뜨지 않는다. 왜???????

 

아래의 글은 이것의 원인을 밝히기 위한 삽질이다.

2021.11.26 - [이슈] - Kotlin으로 백준 문제를 풀다가 생긴 의문에 관하여

 

코드1(통과)

import java.util.*
var answer=0
val toUse = BooleanArray(10)
fun permutation(len : Int, end : Int, m : Int, cnt : Int){
    if(len==end){
        if(cnt==m)answer++
        return
    }
    for(i in 0 .. 9){
        if(toUse[i]){
            toUse[i]=false
            permutation(len+1, end,m, cnt+1)
            toUse[i]=true
        }
        else{
            permutation(len+1,end,m,cnt)
        }

    }
}
fun main() =with(System.out.bufferedWriter()){
    val br = System.`in`.bufferedReader()
    val (n,m) = br.readLine().split(' ').map{it.toInt()}
    if(m!=0){
        val tk =StringTokenizer(br.readLine())
        while(tk.hasMoreTokens()){
            toUse[tk.nextToken().toInt()]=true
        }
    }
    permutation(0,n,m,0)
    write("$answer")
    close()
}

코드2(통과)

import java.util.StringTokenizer

var cnt=0
val toUse = ArrayList<Int>()
var result =ArrayList<Char>()
//tailrec 쓰나 안 쓰나 큰 차이 없었다
tailrec fun permutation(len : Int, end : Int){
    if(len==end){
        var canPass=true
        for(num in toUse){
            if(result.indexOf((num+Character.getNumericValue('0')).toChar())==-1){
                canPass=false
                break
            }
        }
        if(canPass)cnt++
        return
    }
    for(i in 0 .. 9){
        result.add((i+Character.getNumericValue('0')).toChar())
        permutation(len+1, end)
        result.removeAt(result.size-1)
    }
}
fun main() =with(System.out.bufferedWriter()){
    val br = System.`in`.bufferedReader()
    val (n,m) = br.readLine().split(' ').map{it.toInt()}
    if(m!=0){
        val tk = StringTokenizer(br.readLine())
        while(tk.hasMoreTokens()){
            toUse.add(tk.nextToken().toInt())
        }
    }
    permutation(0,n)
    write("$cnt")
    close()
}

코드3(메모리 초과)

import java.util.StringTokenizer

var cnt=0
val toUse = ArrayList<Int>()
var result =""
fun permutation(len : Int, end : Int){
    if(len==end){
        var canPass=true
        for(num in toUse){
            if(result.indexOf(num.toString())==-1){
                canPass=false
                break
            }
        }
        if(canPass)cnt++
        return
    }
    for(i in 0 .. 9){
        result += i.toString()
        permutation(len+1, end)
        result = result.dropLast(1)
    }
}
fun main() =with(System.out.bufferedWriter()){
    val br = System.`in`.bufferedReader()
    val (n,m) = br.readLine().split(' ').map{it.toInt()}
    if(m!=0){
        val tk = StringTokenizer(br.readLine())
        while(tk.hasMoreTokens()){
            toUse.add(tk.nextToken().toInt())
        }
    }
    permutation(0,n)
    write("$cnt")
    close()
}