백준 7490 0 만들기 Kotlin (백트래킹)

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

7490번: 0 만들기

문제

1부터 N까지의 수를 오름차순으로 쓴 수열 1 2 3 ... N을 생각하자.

그리고 '+'나 '-', 또는 ' '(공백)을 숫자 사이에 삽입하자(+는 더하기, -는 빼기, 공백은 숫자를 이어 붙이는 것을 뜻한다). 이렇게 만든 수식의 값을 계산하고 그 결과가 0이 될 수 있는지를 살피자.

N이 주어졌을 때 수식의 결과가 0이 되는 모든 수식을 찾는 프로그램을 작성하라.

입력

첫 번째 줄에 테스트 케이스의 개수가 주어진다(<10).

각 테스트 케이스엔 자연수 N이 주어진다(3 <= N <= 9).

출력

각 테스트 케이스에 대해 ASCII 순서에 따라 결과가 0이 되는 모든 수식을 출력한다. 각 테스트 케이스의 결과는 한 줄을 띄워 구분한다.

알고리즘 분류

• 구현
• 문자열
• 브루트포스 알고리즘
• 백트래킹

풀이

숫자는 1부터 N까지 고정이다.

그럼 우린 그 사이에 들어갈 연산자의 순열만 구해주면 된다.

재귀함수를 이용해 연산자들의 순열을 구해주자. (backTracking 함수)

이제 연산자들의 순열과 1부터 N까지의 숫자를 이용해 0이 되는지 계산하고, 0이 된다면 그 계산 식을 출력하면 된다.

계산과 출력은 구현의 영역이니 코드를 참고하는 게 좋을 것 같다.

간략히 설명하자면 공백 연산을 먼저 처리하여 n - 공백 연산 갯수 크기의 리스트로 압축하고나서 +,- 연산을 수행하여 0이 나오는지 체크한다. 그리고 0이 나온다면 숫자와 연산을 순서대로 번갈아가며 출력한다. 

 

코드

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

val operators = arrayOf(
    ' ',
    '+',
    '-'
)

fun main() {
    val bw = System.out.bufferedWriter()
    repeat(getInt()){
        val n = getInt()
        backTracking(1,CharArray(n-1){' '}, n, bw)
        bw.newLine()
    }
    bw.close()
}

fun backTracking(num: Int, opArr: CharArray, n: Int, bw: BufferedWriter) {
    if (num == n) {
        if(cal(opArr,n)) {
            for (i in 0 until n) {
                bw.write("${i+1}")
                if (i in opArr.indices)
                    bw.write("${opArr[i]}")
            }
            bw.newLine()
        }
        return
    }
    for (i in 0..2) {
        opArr[num-1] = operators[i]
        backTracking(num+1, opArr, n,bw)
    }
}

fun cal(opArr: CharArray, n: Int): Boolean {
    val numArr = IntArray(n){it+1}
    for(i in opArr.indices){
        when(opArr[i]){
            ' '->{
                numArr[i] = numArr[i]*10 + numArr[i+1]
                numArr[i+1] = 0
            }
        }
    }
    val compressedNumArr = numArr.filter { it != 0 }.toMutableList()
    val compressedOpArr = opArr.filter { it!=' ' }
    for(i in compressedOpArr.indices){
        when(compressedOpArr[i]){
            '+' ->{
                compressedNumArr[i+1] = compressedNumArr[i] + compressedNumArr[i+1]
            }
            '-' ->{
                compressedNumArr[i+1] = compressedNumArr[i] - compressedNumArr[i+1]
            }
        }
    }
    return compressedNumArr[compressedNumArr.size-1] == 0
}