[백준] 1541번 : 잃어버린 괄호 / 그리디(Greedy) 알고리즘 / 파이썬 Python

문제

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

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

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

입력

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

출력

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

 

---

★핵심 : 한번 빼기가 나온 이후로는 전부 빼주면 됨

 

 

내 코드 

 

equation = list(input())

num = ''
status = 0
result = 0
number = ['0','1','2','3','4','5','6','7','8','9']

for e in equation:
    if e in number :
        num += e
        continue
    elif e == '-' and status == 0:
        result += int(num)
        num=''
        status = 1
        continue
    if status == 0:
        result += int(num)
        num = ''
    elif status == 1:
        result -= int(num)
        num = ''    

if status == 0 :
    result += int(num)
elif status == 1:
    result -= int(num)

print(result)

맞긴 한데, 너무 길다.

 

 

모범 코드

 

equation = input().split('-') 
result = 0 
for i in equation[0].split('+'):
    result += int(i) 

for i in equation[1:]: 
    for j in i.split('+'): 
        result -= int(j) 

print(result)

★ 핵심 : 한번 빼기가 나온 이후로는 전부 빼주면 됨

★ 애초에 입력받을때 - 를 기준으로 입력받으면 됨

 

예1 ) 55-40+50 

    '-' 기준으로 입력받으면 equation = [55, 40+50]

 

    equation의 0번째 원소는 -가 나오기 전까지의 숫자 혹은 숫자의 합이다. 

    equation[0] = 55 

    equation[0].split('+') = 55

    i = 55 : result = 55

    백ㅈ

    equation의 1번째 원소부터 끝까지는 전부 빼주면 된다.

    i = 40+50

        j = 40 : result = 55-40 = 15

        j = 50 : result = 15-50 = -35

예2 ) 15+55-40+50

    '-' 기준으로 입력받으면 equation = [15+55, 40+50]

    equation의 0번째 원소는 -가 나오기 전까지의 숫자 혹은 숫자의 합이다. 

    equation[0] = 15+55 

    equation[0].split('+') = 15, 55

    i = 15 : result = 15

    i = 55 : result = 15+55 = 70

 

    equation의 1번째 원소부터 끝까지는 전부 빼주면 된다.

    i = 40+50

        j = 40 : result = 70-40 = 30

        j = 50 : result = 30-50 = -20