[파이썬] 백준 1541 : 잃어버린 괄호

[파이썬] 백준 1541 : 잃어버린 괄호

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

1541번: 잃어버린 괄호

실버2

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

---

접근

최솟값으로 만들려면 빼는 부분의 값이 커야한다.

우선 입력받은 값을 마이너스를 기준으로 구분해야 하고,

나누어진 오른쪽 부분의 모든 값을 전부 더해준다음, 맨 처음 값에다가 빼주면 된다.

 

55-50+40의 경우,

-를 기준으로 나누면

55, 50+40이 된다.

 

50+40을 더하면 90이 되고, 이를 다시 55에다가 빼주면 55-90 = -35가 나온다.

 

 

코드 풀이(92ms)

import sys
cal = sys.stdin.readline().rstrip().split('-')

for i in range(len(cal)):
    cal[i] = sum(list(map(int, cal[i].split('+'))))

for i in range(1, len(cal)):
    cal[0] -= cal[i]
print(cal[0])

 

1. -를 기준으로 항을 나눈다.

2. +기준으로 각 항을 다시 나눈후, 각항의 총합을 재할당한다.

3. 맨 왼쪽값에 나머지 원소들의 값을 연속으로 뺄샘 계산한다.

 

split함수를 이용해 '-'를 기준으로 입력받은 문자열을 나눈다.

55-50+40의 경우 cal = ['55', '50+40']로 나뉘어진다.

 

오른쪽에 있는 값을 전부 더하기위해 '+'를 기준으로 각각의 원소를 나눈후, sum()함수로 각 원소의 총합을 재할당한다.

따라서 cal = [55, 90]이 된다.

이는 -를 기준으로 각항을 나눈 후, - 오른쪽의 항들을 괄호를 씌워 모두 더해준 것과 같다.

 

어떤 값을 입력으로 받더라도 cal[0]은 연산자, 나머지 원소는 피연산자가 되어야하므로

cal[0]에다가 나머지의 원소들을 전부 뺄샘으로 계산하는 것을 반복한다.

만약 입력값이 55-50+40-30+40처럼 -가 복수로 존재하더라도 55-(90)-(70) = -105와 같은 계산을 할 수있게 된다.

 

 

다른 사람 코드(68ms)

arr = input().split('-') 
s = 0 
for i in arr[0].split('+'): 
    s += int(i) 
for i in arr[1:]: 
    for j in i.split('+'): 
        s -= int(j) 
print(s)

 

먼저 -를 기준으로 나누는 것은 동일하다.

그렇게 나뉜 왼쪽 항을 +를 기준으로 전부 쪼개고, 쪼개진 값들을 모두 더해 s에 할당한다.

 

최초에 -를 기준으로 나누어진 오른쪽 항 또한 +를 기준으로 전부 쪼개고, s에 대한 뺄셈을 반복한다.

 

내 방법은 두번째 쪼개기를 -의 왼쪽 오른쪽 항을 동시에 진행하는 방법이었으나 후자의 방법이 조금 더 빨랐다.