잃어버린 괄호 - 1541
링크: 1541, 잃어버린 괄호
문제 정의
양수와 +,-를 이용한 수식에 괄호를 적절히 사용하여 최솟값이 출력되도록 하는 문제이다.
문제 풀이
예제 입력인 55-50+40을 보면 50과 40을 괄호로 묶어 최솟값 35를 출력했다.
이것을 보며 유추할 수 있는 것은 -부호가 등장한 이후 숫자를 모두 더한 후 빼줬다는 것이다.
이것을 일반화 해보면 -가 처음 등장하는 숫자부터 -가 다시 한번 등장하는 숫자까지 괄호를 묶어주면 최솟값이 된다. 즉, -와 -사이의 값을 괄호로 묶어주면 된다는 것이다.
ex) 30 + 20 - 40 + 30 - 50 → 30 + 20 -(40 + 30) - 50
위 예제를 좀 더 일반화를 시켜보면 -부호가 처음 등장하는 숫자를 모두 빼는 것과 같으므로, -부호가 처음 등장하는 숫자부터 끝까지 괄호를 묶어줘도 수학적으로 같다는 의미가 된다.
ex) 30 + 20 -(40 + 30) - 50 = 30 + 20 -(40 + 30 + 50) = 30 + 20 - 40 - 30 - 50
이러한 과정을 통해 알 수 있는 것은 -부호가 처음 등장하는 부분을 기준으로 두 덩어리로 나눌 수 있다.
첫번째 덩어리(30, 20), 두번째 덩어리(40, 30, 50)
이러한 과정을 통해 각 덩어리는 덧셈 연산만 수행하고, 마지막에 두 덩어리를 빼주면 되도록 문제를 단순화 시킬 수 있게 되었다.
import Foundation
// ex)55-50+40
let input = readLine()!
// -를 기준으로 두 개의 덩어리(배열)로 만들어줌
let minusParts = input.components(separatedBy: "-").map {
$0.components(separatedBy: "+").map { Int($0)! }
}
// minusParts: [[55], [50, 40]]
/// 첫 번째 덩어리 모두 더해줌
/// reduce(0, +): 0부터 시작해서 배열의 요소 모두 더하는 작업(0 + 55)
var result = minusParts[0].reduce(0, +)
for part in minusParts.dropFirst() { // dropFirst(): 첫번째 배열은 버리고 나머지 배열 반환
/// 두번째 덩어리 모두 더한 후 빼기 진행
result -= part.reduce(0, +)
}
print(result)느낀점
이번 문제를 풀면서 사람이 보기엔 매우 간단한 문제임에도 불구하고, 프로그래밍으로 구현하기 위해서는 이 간단한 문제 속에서도 규칙성을 찾아내고 일반화를 해야 함을 느꼈다. 물론, 코딩할때마다 언제나 느끼는 거지만, 추상화가 적은 문제일수록 이러한 현상이 더 발현되는 것 같다.
모든 분야가 그렇겠지만, 복잡한 문제를 단순화할 수 있는 추상화적 사고 능력을 기르기 위해 문제들을 풀고 공부해야 되겠다는 생각이 더 강해지는 문제였다.
