[백준/Python]1514: 잃어버린 괄호

문제

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

백준 문제집 - 0x11강 - 그리디

 

알고리즘: 그리디, 문자열

---

풀이

세준이는 양수와 +, -, 그리고 괄호를 가지고 식을 만들었다. 그리고 나서 세준이는 괄호를 모두 지웠다.
그리고 나서 세준이는 괄호를 적절히 쳐서 이 식의 값을 최소로 만들려고 한다.
괄호를 적절히 쳐서 이 식의 값을 최소로 만드는 프로그램을 작성하시오.

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

괄호를 적절하게 넣어 최소값으로 만들어야한다. 연산자는 +, - 둘뿐이다.

그렇다면 - 기호가 나올때마다 괄호로 묶어줘서 음수값을 최대한 크게 만들면 되겠다.

 

예제 1: 55 - 60 + 40 => 55 - (60 + 40)

 

또한 입력 데이터 조건을 잘 보면 "가장 처음과 마지막 숫자는 숫자"라고 되어있다.

즉, 첫번째 값으로 음수가 나올 일은 없다.

따라서 입력받은 식을 -를 기준으로 분리하면 첫번째 숫자를 제외한 나머지 요소들은 모두 괄호로 묶을 수 있는 숫자들이 된다.

 

예를들어, 30 - 50 - 70 + 10 + 20 - 10 이 주어진다고 생각해보자.

분리 후의 결과는 [30, 50, 70+10+20, 10] 이 될것이다.

첫번째 숫자 30은 무조건 양수이므로 결과값에 미리 더해준다.

두번째 ~ 마지막 요소들은 모두 -() 안에 들어갈 수 있는 묶음들이다. 해당 묶음의 숫자들을 모두 더하고 이 값만큼을 빼준다.

 

전체 코드

# 메모리: 31120KB / 시간: 44ms

expression = input().split("-")
lst = []

for ex in expression:
    lst.append(sum(map(int, ex.split("+"))))

ret = lst[0]

for l in lst[1:]:
    ret -= l

print(ret)

참고로 인덱싱이 아닌 슬라이싱은 범위를 벗어나도 에러를 뱉어내지 않는다.

만약 lst = [30] 인 상황이어도 lst[1:]은 빈 리스트 [ ]를 반환한다.