[Algorithm] [Python&Swift] 백준/BOJ - 1541 _ 잃어버린 괄호

1541 - 잃어버린 괄호

 

문제

---

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

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

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

 

입력

---

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

 

출력

---

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

 

제출코드

---

Python

arr = input().split("-")
result = 0
tmp_arr = []
for char in arr:
    tmp_sum = 0
    tmp = char.split("+")
    for item in tmp:
        tmp_sum += int(item)
    tmp_arr.append(tmp_sum)

result += tmp_arr[0]
for i in range(1, len(arr)):
    result -= tmp_arr[i]
print(result)

 

Swift

func main() -> Int {
    let arr = readLine()!.split(separator: "-")
    var result = 0
    var tmp_arr = [Int]()
    for char in arr {
        var tmp_sum = 0
        let tmp = char.split(separator: "+")
        for item in tmp {
            tmp_sum += Int(item)!
        }
        tmp_arr.append(tmp_sum)
    }
    result = tmp_arr[0]
    for i in 1..<tmp_arr.count {
        result -= tmp_arr[i]
    }
    return result
}
print(main())

 

문제풀이

---

주어진 문자열에서 최소의 값을 만들어내기 위해서는 -를 기준으로 괄호를 치면 된다.

예시를 살펴보자.

55-50+40 이 입력으로 들어왔을떄 이를 최소로 만들기 위해서는 55-(50+40) 와 같이 괄호를 쳐야한다.

보다 복잡한 식을 예시로 살펴보자.

55-50+40-30-20 이 입력으로 들어왔다면, - 기준으로 괄호를 치게 되면 55-(50+40)-(30)-(20) 이와 같이 괄호가 쳐지며 해당 연산의 결과가 최소값이다.

따라서, 값을 입력받을때 -를 기준으로 split한다.

이후, 배열의 원소 중 + 연산자가 포함된 원소는 값을 게산해서 배열에 저장해놓는다.

55-50+40 의 경우 위 연산들을 진행하면 [55, 90] 으로 정리된다.

arr[0]의 값은 덧셈으로 진행해주고 이후의 모든 원소들을 - 연산을 진행해준다.