#14888 연산자 끼워넣기

문제

---

 

 

코드

---

const val MAX = 1_000_000_000
const val MIN = -1_000_000_000
fun main() = with(System.`in`.bufferedReader()) {
    val n = readLine().toInt()
    val num = readLine().split(' ').map { it.toInt() }
    val op = readLine().split(' ').map { it.toInt() }.toIntArray()
    var max = MIN
    var min = MAX

    fun dfs(count: Int, temp: Int, opIndex: Int) {
        val result = when (opIndex) {
            0 -> temp + num[count]
            1 -> temp - num[count]
            2 -> temp * num[count]
            3 -> temp / num[count]
            else -> temp
        }
        if (count == n - 1) {
            if (result > max) max = result
            if (result < min) min = result
            return
        }
        for (i in op.indices) {
            if (op[i] != 0) {
                op[i]--
                dfs(count + 1, result, i)
                op[i]++
            }
        }
    }
    dfs(0, num[0], -1)
    println(max)
    println(min)
}

 

풀이

---

 

처음에 제출한 코드는 좀 복잡했다.

생각나는대로 구현하다 보니 쓸데없는 메모리 사용도 많았고 가독성도 좋지 않았다.

import java.util.*

const val MAX = 1_000_000_000
const val MIN = -1_000_000_000
fun main() = with(System.`in`.bufferedReader()) {
    val n = readLine().toInt()
    val num = readLine().split(' ').map { it.toInt() }
    val op = readLine().split(' ').map { it.toInt() }.toIntArray()
    val dq: Deque<Int> = ArrayDeque()
    val visited = op.copyOf()
    var max = MIN
    var min = MAX

    fun cal() { 
        val opList = ArrayDeque<Int>()
        for (e in dq) opList.add(e)
        var result = num[0]
        for (i in 1..<n) {
            when (opList.pollFirst()) {
                0 -> result += num[i]
                1 -> result -= num[i]
                2 -> result *= num[i]
                3 -> {
                    if (num[i] < 0) {
                        result /= num[i] * (-1)
                        result *= (-1)
                    } else result /= num[i]
                }
            }
        }
        if (result > max) max = result
        if (result < min) min = result
    }

    fun dfs() {
        var empty = true
        for (e in visited) {
            if (e != 0) empty = false
        }
        if (empty) {
            cal()
            return
        }
        for (i in visited.indices) {
            if (visited[i] != 0) {
                visited[i]--
                dq.addLast(i)
                dfs()
                visited[i]++
                dq.removeLast()
            }
        }
    }
    dfs()
    println(max)
    println(min)
}

이렇게 구현할 때, 문제점(?)들을 찾아서 정리해보고자 한다.

우선 덱(deque)을 사용한 이유는 dfs 함수에서는 스택처럼 사용해야했고, cal 함수에서는 큐처럼 사용해야했기 때문에 덱을 사용했다.

op를 복사(visited)한 이유는 재귀함수로 들어갔을 때, 값이 직접적으로 변경됐을 때 문제가 생길까봐 그렇게 했던 것 같다..ㅎㅎ

다시 생각해보니 어처피 다시 복구를 해주기 때문에 아무런 문제가 없는게 맞았다.

그래서 바로 지웠음

 

cal 함수에서 dq를 복사한 이유는

원래 함수의 인자로 dq를 넘겨줬는데, 코틀린에서는 인자로 전달될 때 얕은 복사가 디폴트라고 하더라

그래서 그런지 cal 함수가 실행되고 나서 dfs에서 dq.removeLast()를 할 때 오류가 발생했다.

이미 cal 함수에서 전부 pop되어 빈 덱이기 때문..

 

기본 타입(primitive type)은 인수로 넘겨줬을 때 값이 복사되어 깊은 복사라고 할 수 있지만,

그 이외에는 얕은 복사라서 덱을 pop하면 원래 객체에도 영향이 가게 된다..

그래서 직접 값을 전부 복사해줘서 사용했다.

 

코드가 너무 지저분하고 가독성이 떨어지는 것 같아서 다른 사람의 코드를 구경하다가 깨달은 사실

dfs의 인자로 계산된 값을 넘겨주면 cal 함수 자체가 필요없다는 사실ㅎㅎ

그리고 cal 함수는 물론이고 덱을 복사할 필요도 없고, 덱 자체도 필요없게 된다

연산자를 저장하는 것 대신 값을 저장해서 넘겨주기 때문!

 

많이 연습하다보면 빠르고 간단하게 구현할 수 있을 것 같다