1541번: 잃어버린 괄호

1541번: 잃어버린 괄호

 

 

잃어버린 괄호 

 

문제

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

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

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

입력

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

출력

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

예제 입력 1 

55-50+40

예제 출력 1 

-35

 

---

풀이 

 

 

문제를 확인해보자.

 

• 양수, +, - 가 있는 식에서 괄호를 적절히 사용하여 식의 값을 최소로 만들어라.

 

여기서 중요하게 생각해야하는게 바로 "괄호"이다.

 

처음 내 생각

 

 

처음에 생각한 건 (-)는 음수, (+)는 양수로 저장하여 dp로 탐색을 하면서 최솟값을 구하려했다.

 

let input: String = readLine()!

var arr: [Int] = []
var num:String = ""

for inputValue in input{
    
    if inputValue == "-" {
        arr.append(Int(inputValue))
        num = ""
    }
    
    if inputValue == "+"{
        arr.append(Int(inputValue))
        print(num)
        num = ""
    }
    else{
        num = num + String(inputValue)
    }
}

print(num)

 

예를들어, 예제1의 입력값 55-50+40을 입력하면 [55,-50,40]의 값을 배열에 저장한다.

그리고 dp로 배열에 저장된 값을 더하면서 가장 최소가 되는 값을 구하려고 했는데, 여기서 오류가 있다.

 

"괄호"가 중요하다고 했는데, dp로 저장된 값을 더하게되면 55-(50+40)과 같이 괄호를 넣은 값을 구할 수 없다.

 

 

 

---

설계

 

이제 괄호의 중요성을 알게되었다. 어떻게 구현할까?

 

먼저, 다음과 같은 경우를 생각해보자.

 

55-50+40-30+20+10

 

 

• 초록색(-)는 빨간색(-)를 만나기 전까지의 합을 더하는 것이 최솟값이 된다. => -(50+40)
• 빨간색(-)도 마지막 숫자까지 더한 값이 최솟값이 된다. => -(30+20+10)

 

즉, (-)가 있을 때 다음(-)를 만나기 전까지 값들을 모두 더해주고 결과값에서 빼면 된다.

 

 

---

구현

 

55-50+40-30+20+10

 

위의 예제를 생각해보자.

 

 

1. "-" 구분하여 입력받기

 

let input = readLine()!.split(separator: "-").map({String($0)})

 

• input = [55, 50+40, 30+20+10]

 

 

2. "+" 구분하여 입력받기

 

for i in 0..<input.count{
    let n = input[i].split(separator: "+").map({Int(String($0))!})

    ...
}

 

i	0	1	2
n	[55]	[50,40]	[30,20,10]

 

 

3. 초기값 세팅

 

첫번째 값은 항상 양수이기때문에 i=0일 때, n 값을 다 더한다.

 

 

4. 최솟값 탐색

 

i!=0이라면, (-)를 가진 값이니 해당 n 값들을 다 더한 후 결과값에서 빼준다. 

 

 

---

전체코드

 

let input = readLine()!.split(separator: "-").map({String($0)})

var arr: [Int] = []

var result = 0


for i in 0..<input.count{
    let n = input[i].split(separator: "+").map({Int(String($0))!})

    if i==0{
        result += n.reduce(0, +)
    }
    else{
        result -= n.reduce(0, +)
    }
}
print(result)