[Kotlin] 백준(BOJ) 1541 잃어버린 괄호

문제 전문은 아래 버튼을 눌러 확인하실  수 있습니다.

문제

세준이는 양수와 +, -, 그리고 괄호를 가지고 식을 만들었다. 그리고 나서 세준이는 괄호를 모두 지웠다.

그리고 나서 세준이는 괄호를 적절히 쳐서 이 식의 값을 최소로 만들려고 한다.

괄호를 적절히 쳐서 이 식의 값을 최소로 만드는 프로그램을 작성하시오.

입력

첫째 줄에 식이 주어진다. 식은 ‘0’~‘9’, ‘+’, 그리고 ‘-’만으로 이루어져 있고, 가장 처음과 마지막 문자는 숫자이다. 그리고 연속해서 두 개 이상의 연산자가 나타나지 않고, 5자리보다 많이 연속되는 숫자는 없다. 수는 0으로 시작할 수 있다. 입력으로 주어지는 식의 길이는 50보다 작거나 같다.

출력

첫째 줄에 정답을 출력한다.

예제 입출력

문제 해설

직관적으로 봤을 때, 덧셈은 교환 법칙이 성립하기 때문에 괄호로 계산 결과를 어떻게 바꾸는지 혼동이 있을 수도 있다. 하지만 문제

어찌 보면 당연한 것이기도 하지만, 숫자와 부호를 쪼개서 괄호를 배치할 수 있다는 부분만 염두에 두면 문제 이해에 도움이 될 것이라 생각한다. 

예제1을 예로 들면 $55-55+40$ 에서 최소의 결과를 도출하기 위해서는 마이너스의 뒷 부분을 가장 크게 만들면 된다. 따라서 $55-(55+40) = -35$ 가 최소일 것이다. 

 

이를 통해 도출해낼 수 있는 문제 해결 발상은 생각보다 간단하다. 바로 적게 더하고 많이 빼면 된다. 구현 방법은 여러가지가 있을 수 있겠으나, 분할 정복 방법으로 해결해봤다. 마이너스를 기준으로 식을 나눈 뒤 각각의 식을 최대가 되도록(앞에 마이너스가 있으므로) 하면 될 것이다. 

 

구체적으로 다음과 같이 로직을 설계해봤다. 

 

1. 식을 - 를 기준으로 분할한다. 

2. 분할된 식들을 최대로 만든다(문제에서는 +, 숫자로만 이루어져있을 것이기 때문에 그냥 더하면 된다)

3. 이를 그대로 다시 계산한 값이 최소일 것이다. 

소스 코드

 

fun main() {
	// 마이너스를 기준으로 식을 분할
    val groups = readln().split("-")
	
    // 음수로 시작하지 않으므로 첫 번째 그룹은 그냥 계산해서 더한다
    var result = groups.first().split("+").sumOf { it.toInt() }
    val elseGroups = groups.drop(1)

	// 2번째 그룹부터는 최대로 만들어서 빼준다
    for(i in elseGroups.indices) {
    	// 문제에 별다른 조건이 없으므로 그냥 더한 값이 최대이다. 
        result -= elseGroups[i].split("+").sumOf { it.toInt() }
    }
    print(result)
}

 

 

시간 복잡도

for문 내부에 문자열을 순회하는 split() 메서드가 있기 때문에 $O(N^2)$ 으로 오해할 수 있지만, 이를 다시 생각해보면 결국 하나의 문자열을 그룹화해서 따로 순회한다는 말이므로 입력 문자열의 길이에 비례할 것으로 생각된다. 때문에 $O(N)$이다.