[백준 15659] - 연산자 끼워넣기(3)(Kotlin)[골드4]

문제

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

15659번: 연산자 끼워넣기 (3)

문제 풀이

정말 까다로운 문제였다. 연산자들의 우선순위를 해결해줘야 했기에, 그 부분에서 사람들이 많이 어려움을 느꼈을 것이라고 생각한다.

dfs를 이용해서 모든 경우의 수를 탐색하고, 해당 식의 최솟값과 최댓값을 구한다.

초기 풀이 방식에서는 숫자와 연산자들을 모두 포함하는 배열을 하나 생성했지만, 숫자들은 고정이고, 연산자들의 순서 조합만 바뀐다고 생각했기에, 연산자들의 조합만 신경 썼다.

 

기존 : 1+2+3%4*5-6
수정 : ++%*-

 

 

연산자들이 다 정해졌다면, 이제 연산을 해야 하는데, 연산자들은 우선순위가 있다는 점에 주목해야 한다.

['*'] == ['/'] >  ['+'] == ['-']이고, 우선순위가 같다면 먼저 나오는 연산자부터 처리해야 한다.

따라서 나는 *와 /를 추출해서 먼저 계산해 줬고, +와 -는 *,/를 계산하고 난 뒤의 한번 더 과정을 거쳐서 계산했다.

 

위의 예를 들어서 설명해 보겠다.

 

최종식 : 1+2+3%4*5-6 , operators :++%*- , numbers : 1,2,3,4,5,6 , saveNum : [] , saveOp : []

 

검사를 시작하기 전에 첫 번째 숫자를 saveNum에 넣어준다. -> saveNum [1]

연산자를 검사하는데 경우의 수는 2가지가 있을 것이다.

1. +,- 인 경우
2. *,/인 경우

우선 더하기와 빼기 인 경우 뒤에 곱하기와 나누기가 있을 경우 우선순위에 있어 밀린다. 그래서 계산을 하면 안 되기에,

연산자와 숫자를 각각 saveNum, saveOp에 넣어준다. -> saveNum [1,2] , saveOp : [+]

뒤 글자도 +이기에 앞의 과정을 그대로 해준다. -> saveNum [1,2,3] , saveOp : [+,+]

다음 연산자는 % 이다. 위에서 *와 %는 바로바로 연산해 준다고 했기 때문에, 

saveNum에 가장 최근에 저장된 숫자와 다음 숫자를 연산해서 saveNum에 넣어준다. 

그리고 바로 연산을 하기 때문에 saveOp에 저장해 줄 필요는 없다. -> saveNum [1,2,3], saveOp [+,+]

다음 연산자는 *이다. % 와 동일하게, 가장 최근에 저장된 숫자와 다음 숫자를 연산하고 그 결과를 넣어준다.

-> saveNum [1,2,15], saveOp [+,+]

다음은 -이다. -는 숫자와 연산자를 그대로 저장한다. -> saveNum [1,2,15,6]  saveOp [+,+,-]

saveNum과 saveOp를 보면 알 수 있듯이 항상 숫자는 연산자의 개수보다 한 개 많아야 한다. 

만약 이 조건이 성립하지 않는다면 잘못 처리한 것이다.

 

앞 과정에서는 곱하기와 나누기를 처리했다면 이젠 남은 더하기와 빼기를 처리하면 된다.

앞에서부터 시작하는 것이 옳다.

왜냐하면 뒤에서부터 시작한다면 3-3+6의 결과가 -6이 나오기 때문이다.

 

saveNum에서 앞에서 2개의 숫자를 빼고, 연산자에 맞게 연산을 하고, 그 결과를 맨 앞에 넣어준다.

이러한 과정을 계속 반복하다가, saveOp가 더 이상 없다면 종료하고 saveNum에 가장 앞에 있는 원소를 반환해 준다.

 

글로 설명해서 엄청 복잡해 보이지만, 간단하게 그림을 그려서 차근차근 따라 해보면 간단한 문제이다.

 

문제에서 중요한 점은 곱하기와 나누기를 어떻게 처리하냐라고 생각한다.

나는 더하기와 나누기보다 먼저 계산하고, 남은 더하기와 나누기를 처리하는 방식을 택했다.

 

문제 코드

import java.io.BufferedReader
import java.io.InputStreamReader
import kotlin.math.max
import kotlin.math.min

class `15659`(){
    private val br = BufferedReader(InputStreamReader(System.`in`))
    private var n = 0
    private lateinit var array : Array<Int>
    private val operators : Array<Int> = Array(4,{0})
    var minResult = Int.MAX_VALUE
    var maxResult = Int.MIN_VALUE
    private var expression = ""
    private val numStack : MutableList<Int> = mutableListOf()
    private val tempOperatorStack : MutableList<Char> = mutableListOf()
    init{
        input()
        backtracking(0)
    }
    private fun input(){
        n = br.readLine().toInt()
        array = Array(n,{0})
        var line = br.readLine().split(" ")
        for(i in 0 until n){
            array[i] =line[i].toInt()
        }
        line = br.readLine().split(" ")
        for(i in 0 until 4){
            operators[i]=line[i].toInt()
        }
    }
    private fun backtracking(depth : Int){
        if(depth==n-1){
            val result = calculate()
            minResult = min(minResult,result)
            maxResult = max(maxResult,result)
            return
        }
        else{
            for(i in operators.indices){
                if(operators[i]==0)
                    continue
                var op = ""
                when(i){
                    0->op="+"
                    1->op="-"
                    2->op="*"
                    3->op="/"
                }
                operators[i]--
                expression+=op
                backtracking(depth+1)
                expression=expression.dropLast(1)
                operators[i]++
            }
        }
    }
    private fun calculate() : Int{
        numStack.add(array[0])
        for(i in expression.indices){
            when(expression[i]){
                '*'->{numStack.add(numStack.removeLast()*array[i+1])}
                '/'->{numStack.add(numStack.removeLast()/array[i+1])}
                '+'->{
                    numStack.add(array[i+1])
                    tempOperatorStack.add('+')
                }
                '-'->{
                    numStack.add(array[i+1])
                    tempOperatorStack.add('-')
                }
            }
        }
        while(!tempOperatorStack.isEmpty()){
            val now=tempOperatorStack.removeFirst()
            when(now){
                '+'->{
                    val num1= numStack.removeFirst()
                    val num2= numStack.removeFirst()
                    numStack.add(0,num1+num2)
                }
                '-' ->{
                    val num1=numStack.removeFirst()
                    val num2=numStack.removeFirst()
                    numStack.add(0,num1-num2)
                }
            }
        }
        return numStack.removeFirst()
    }
}
fun main(){
    val solution = `15659`()
    print("${solution.maxResult}\n${solution.minResult}")
}