[Swift Algorithm] 잃어버린 괄호 BOJ #1541

문제 설명

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

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

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

 

입력

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

 

출력

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

 

입출력 예제

입력

55-50+40

출력

-35

 

내 문제 풀이

import Foundation

var input = readLine()!.split(separator: "-").map({String($0)}) // "-" 기준으로 나눠 배열 생성
var sum = 0
var tmp = 0

for i in 0..<input.count {
    let n = input[i].split(separator: "+").map({Int(String($0))!}) // "+"로 다시 한 번 나누기
    for j in n { tmp += j } // "+"로 나눈 배열의 모든 요소 더하기
    
    if i == 0 { sum += tmp } // 첫 번째 요소의 경우에만 sum에 더해주기
    else { sum -= tmp } // 첫 번째 요소를 제외, "-"를 기준으로 나눈것이기 때문에 sum에서 빼주기
    tmp = 0 // tmp 초기화
}

print(sum)

👉 괄호는 무조건 "-" 뒤부터 다음 "-"가 나오기 전까지 묶어줘야 최솟값을 구할 수 있다는 사실이 포인트!

예를들어, 55-50+40 의 경우 55-(50+40) 이렇게 - 뒤의 숫자들을 모두 더해서 빼주면 최솟값,,!

• "-"를 기준으로 괄호를 넣어줄 것이기 때문에, 우선 "-"를 기준으로 나눠 input 배열을 생성했다.
• 그리고 input 배열의 요소마다 "+"를 기준으로 다시 나눠 모든 요소를 Int로 형변환하여 더했다.
• 첫 "-"가 나오기 전까지 나온 숫자들은 sum에 더해주고,
  "-"가 한 번이라도 나온 이후에는 계속 더한 수들을 sum에서 빼주는 것을 반복한다.

 

💡 피드백

• 괄호를 넣어줄 위치만 확인하면 쉽게 풀 수 있는 문제였다.

 

---

 

문제

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