<백준> 0 만들기(Gold 5)

[백준]

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

[깃허브]

ForCodeKata/baekjoon 문제집/7490 0 만들기 at main · heesoo-park/ForCodeKata

제출 결과

---

어제 풀었던 문제였지만 어쩌다보니 오늘 올리게 되었다.

이 문제는 정말 뭔가 오래 걸렸다.

해결 가닥은 금방 잡았지만 그걸 구현하는 과정이 순탄치 않았기 때문이다.

 

문제를 한번 쭉 읽고 가장 먼저 생각이 든 것은 숫자 제한도 작고 모든 케이스를 훑어봐야할 거 겉아서 재귀를 통한 브루트포스였다.

그래서 1부터 주어지는 숫자까지 재귀를 돌리면서 마지막 숫자에 도달했을 때 연산을 진행하여 0이 되는지 확인하고 결과에 저장하는 방식을 생각했다.

 

그리고 구현을 해나가는 중에 재귀 사이사이에 연산 처리를 해볼까 하고 시도했다가 공백 처리가 복잡해지면서 다시 마지막 숫자에서 한번에 처리하도록 방향을 틀었다.

공백은 연산에 들어가기 전에 replace를 통해 공백을 없애고 연산식을 쭉 읽어나가며 연산자 전까지는 숫자로 바꾸고 연산자가 나오면 연산을 진행했다.

 

글로 정리해서 쓰니까 아주 짧지만 여러 문제들이 있었던 건 팩트다.

연산식을 전역변수로 둘지 매개변수로 둘지, 연산자 저장을 어떤 방식으로 할지, 초기값을 어떻게 할지, 공백을 어떻게 처리할지 등등...

생각보다 자잘한 거에서 많이 걸렸다.

 

해당 방법으로 작성한 코드는 다음과 같다.

import java.io.*
import java.util.*

private val oper = listOf(" ", "+", "-")
private val bw = BufferedWriter(OutputStreamWriter(System.out))

fun main(args: Array<String>) {
    val br = BufferedReader(InputStreamReader(System.`in`))

    val t = br.readLine().toInt()
    repeat(t) {
        val max = br.readLine().toInt()
        makeZero(1, max, "1")
        bw.write("\n")
    }

    bw.flush()
    bw.close()
}

fun makeZero(start: Int, size: Int, exp: String) {
    if (start == size) {
        val sum = calSum(exp)
        if (sum == 0) bw.write("$exp\n")
        return
    }

    for (i in oper) {
        makeZero(start + 1, size, exp + i + (start + 1))
    }
}

fun calSum(exp: String): Int {
    val regex = " ".toRegex()
    var temp = regex.replace(exp, "")
    var sum = 0
    var cur = 0
    var curOper = '+'
    for (i in temp) {
        if (i != '+' && i != '-') {
            cur = cur * 10 + (i - '0')
        } else {
            if (curOper == '+') {
                sum += cur
            } else {
                sum -= cur
            }

            curOper = i
            cur = 0
        }
    }

    if (curOper == '+') {
        sum += cur
    } else {
        sum -= cur
    }
    
    return sum
}