백준 1541번 Swift 알고리즘 연습 - 잃어버린 괄호_그리디

이 문제에서 가장 어려웠던 부분은 괄호를 한 번만 쓰냐 여러번 쓰냐의 문제였다...

사실 괄호를 한 번만 쓴다는 조건은 없었지만 나의 문해력이 문제인건지 아니면 그냥 생각을 많이 하고 싶지 않았던 건지...

단 한 번만 사용해서 최소의 값을 만들어야한다는 생각으로 문제를 풀었었다..!

그러니 계속 문제가 안풀리고... 그러다 괄호를 여러번 써도 된다는 걸 깨닫고 풀었다 ;(

 

 

이 문제를 풀면서 생각한 논리적 흐름은

1. 최소값을 만들기 위해서는 -값이 커야한다.
2. -가 붙은 숫자부터 연속된 +가 끝날때까지의 범위를 괄호로 묶어주면(ex. -1+2+3+...+10-11 -> -(1+2+3+...+10)-11)
3. 마이너스의 값이 최대가 된다.
4. 이처럼 -가 붙은 값부터 다음 -가 나올때까지 전부 같은 배열에 담아주고 더한다.
5. 이 때 처음 값은 괄호없이 숫자가 나온다고 했으니 처음시작부터 첫 -가 나오기 전까지의 값은 전부 양수로 더해준다.(first)
6. 앞의 양수값 first에 minus를 전부 모은 totalMinus를 빼주면 끝

 

 

* 1541번

import Foundation

let input = readLine()!.split(separator: "-").map {String($0)}
let first = input[0].split(separator: "+").map {Int(String($0))!}.reduce(0, +)

var totalMinus = 0

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

print(first-totalMinus)

 

 

정리(Today I Learned)

1. 없음