백준 1541번 파이썬 풀이: 잃어버린 괄호

백준 11723번 집합

 

알고리즘 분류: 수학, 그리디 알고리즘, 문자열, 파싱

 

링크: www.acmicpc.net/problem/1541

 

1541번: 잃어버린 괄호

문제

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

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

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

입력

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

출력

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

 

 

문제 파악

 

이 문제는 주어지는 식에 임의로 괄호를 만들어서 최소값을 가지게 하는 문제이다.

 

어떻게 괄호를 만들어야 최소인 값을 만들 수 있을까 고민을 해보다가 떠오른 생각은

 

- 부호가 나오면 다음 - 부호가 나오기 전까지 모두 괄호안으로 묶어버리는 방법이다.

 

그렇게 하면 어떤 수가 주어져도 가장 최소값을 만들 수 있을것 같다.

 

예를 들면 10 + 20 - 30 + 40 + 50 - 60 + 70 + 80 - 90 이라는 식이 주어진다면

 

10 + 20 - (30 + 40 + 50) - (60 + 70 + 80) - 90 이렇게 묶을 수 있을 것이다.

 

 

코드

# 1541번

expression = input().split("-")

for i in range(len(expression)):
    expression[i] = expression[i].split("+")

total_sum = 0
for i in range(len(expression[0])):
    total_sum += int(expression[0][i])

for i in range(1, len(expression)):
    num_sum = 0
    for j in range(len(expression[i])):
        num_sum += int(expression[i][j])

    total_sum -= num_sum

print(total_sum)

주어지는 입력값을 expression이라는 변수에 담아두고 -가 나올 때 마다 스플릿해준다.

 

이렇게 받아온 리스트의 인덱스들은 문자열로 되어있기 때문에 나중에 쉽게 더해주기 위해서

 

안에있는 +마다 다시 스플릿 해준다.

 

첫 번째 - 부호가 나오기 전에 오는 숫자들은 모두 양수이기 때문에 total_sum의 초기값으로 설정한다.

 

expression의 0번 인덱스의 요소들은 total_sum의 초기값으로 설정되있기 때문에

 

1번 인덱스 부터 마지막 인덱스 까지 반복해가면서

 

안에 요소들을 다 더해서 num_sum 으로 저장하고 이를 total_sum에서 빼준다.

 

마지막으로 total_sum을 출력해주면 된다.

 

예를 들어, 55-50+40 이라는 식이 주어진다면

# 55-50+40
expression = input().split("-")
# ['55', '50+40']

for i in range(len(expression)):
    expression[i] = expression[i].split("+")
# ['55', ['50', '40']]

total_sum = 0
for i in range(len(expression[0])):
    total_sum += int(expression[0][i])
# total_sum = 55

for i in range(1, len(expression)):
    num_sum = 0
    for j in range(len(expression[i])):
        num_sum += int(expression[i][j])
		# num_sum = 90
        
    total_sum -= num_sum
	# total_sum = 55 - 90
    
print(total_sum)
# -35

이렇게 나타낼 수 있을 것이다.