[알고리즘] 백준 1541 잃어버린 괄호 (파이썬 풀이)

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

1541번: 잃어버린 괄호

문제

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

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

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

입력

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

출력

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

 

해결코드

n = input().split('-')
print(n)
num = []
for i in n:
    cnt = 0
    k = i.split('+')
    print(k)
    for j in k:
        cnt += int(j)
    num.append(cnt)
result = num[0]
for i in range(1, len(num)):
    result -= num[i]
print(result)

문제풀이

문제 내용을 요약하자면 덧셈과 뺄셈으로 이루어진 식에서

괄호를 적절히 사용하여 식의 값을 최소로 만들면 되는 문제이다.

나는 한참을 고민하다가 다른 사람들의 해설을 봤다.

 

(+)가 들어간 연산을 우선적으로 다 하면 결국 (-) 연산이 남게 되는데 그렇게 되면

최종적인 연산 값이 최소값이 된다는 것이다.

자세한 건 코드를 보면서 얘기하겠다.

 

 

n = input().split('-') <-- n에 첫 식을 받아주는데, (-)연산을 구분하여 입력받아준다.

ex) 55-50+40 일 경우 --> ['55', '50+40'] 으로 나눠진다.

 

그리고 num이라는 리스트 하나를 생성해준다.

 

이제 n의 원소로 for문을 실행시키는데,

 

cnt라는 변수는 0으로 초기화 시킨다(이 변수의 역할은 (+)연산값들을 더한다)

 

k = i.split('+')

k라는 변수에는 리스트 n의 원소를 또 한번 (+)연산자를 구분하여 새로운 리스트를 저장해준다.

 

ex) n=['55', '50+40'] 일 경우 for문 안에 있으므로

k의 첫 번째 값은 ['55'] 이다. <-- (+)연산이 없으므로 그냥 리스트에 들어감

k의 두 번째 값은 ['50', '40'] 이다. <-- (+)연산을 구분하여 리스트에 들어감

 

이제 k의 원소로 또 for문을 실행하는데

cnt 변수에 k의 원소를 int화 시켜서 더해준다.

그리고 num 리스트에 cnt 값을 원소로 추가해준다.

 

ex) k의 첫 번째 값이 ['55'] 이면 cnt에 55를 더해준다.

(for문을 나와서 num 리스트 원소로 55가 추가됨)

cnt는 다시 0으로 초기화 --> k의 두 번째 값이  ['50', '40'] 이면 cnt에 차례대로 50과 40이 더해짐

(for문을 나와서 num 리스트 원소로 90이 추가됨)

 

모든 for문을 빠져나오면

result라는 변수에 num[0] 값을 저장함

(처음에 주어진 식은 양수로 이루어져있으므로 식의 첫 번째 수(num[0])는 무조건 양수와 (+)연산자로 이루어짐)

 

그리고 for문을 실행시키는데

result값에서 나머지 num의 원소를 빼주는 작업이다.

ex) result = 55 / num[1] = 90 / result - num[1] = -35

 

result값을 출력한다.