분류
그리디 알고리즘(greedy), 수학(math), 파싱(parsing), 문자열(string)
문제 설명
세준이는 양수와 +, -, 그리고 괄호를 가지고 식을 만들었다. 그리고 나서 세준이는 괄호를 모두 지웠다.
그리고 나서 세준이는 괄호를 적절히 쳐서 이 식의 값을 최소로 만들려고 한다.
괄호를 적절히 쳐서 이 식의 값을 최소로 만드는 프로그램을 작성하시오.
입력
첫째 줄에 식이 주어진다. 식은 ‘0’~‘9’, ‘+’, 그리고 ‘-’만으로 이루어져 있고, 가장 처음과 마지막 문자는 숫자이다. 그리고 연속해서 두 개 이상의 연산자가 나타나지 않고, 5자리보다 많이 연속되는 숫자는 없다. 수는 0으로 시작할 수 있다. 입력으로 주어지는 식의 길이는 50보다 작거나 같다.
ㅊ
출력
첫째 줄에 정답을 출력한다.
-35
아이디어
-
'-' 기호 사이에는 전부 괄호로 묶어버리면 항상 양수를 빼는 형태가 되므로 최솟값이 됨
-
식이
55-50+40라면, '-' 바로 뒤에서 괄호를 열고 다음 '-'가 없으므로 끝에서 괄호를 닫아서55-(50+40)을 만들 수 있음 -
19+30-22-45+20-10에 위와 같은 방식으로 괄호를 추가하면19+30-(22)-(45+20)-(10)
내 코드
import sys
input = sys.stdin.readline
mdx = input().rstrip()
result = 0
lst = mdx.split('-') # ['10', '1+10', '19]
for idx, m in enumerate(lst):
temp = sum(list(map(int, m.split("+"))))
if idx == 0:
result += temp
else:
result -= temp
print(result)-
split('-')할 때 '-'가 없으면 오류가 뜰까 해서 '-'가 있는 경우 없는 경우로 코드를 짰었는데, '-'가 없으면 없는 대로 그 하나만 리스트로 저장되는 걸 확인! -
split(separator)에서 separator가 없어도 문제가 없다는 걸 이 문제로 확실하게 기억할 수 있게 됨^,^
다른 사람 코드
pieces = [sum(map(int, exp.split('+'))) for exp in input().split('-')]
print(pieces.pop(0) - sum(pieces))- 진짜 .. 야무지게 간결하다
