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

Python

[Python] 백준 알고리즘 온라인 저지 1541 잃어버린 괄호

1541 잃어버린 괄호

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

1541번: 잃어버린 괄호

괄호를 쳐서 최소가 되는 값을 구하기 위해서는 마이너스되는 값이 클수록 값은 작아지므로 -를 기준으로 문제를 풀이했다.

 

알고리즘 분류

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

---

소스코드

import sys
input = sys.stdin.readline

exp = input().split("-")
s = 0

# 마이너스가 나오기 전까지 혹은 플러스만 있을때
for i in exp[0].split('+'):
    s += int(i)
    
# 마이너스가 있을 때 다음 마이너스가 나오기 전까지 괄호를 쳐서 더함
for i in exp[1:]:
    for j in i.split('+'):
        s -= int(j)
        
print(s)

---

풀이

그리디 알고리즘으로 문자열에 대한 이해가 있어야 했다.

조금 더 복잡한 식으로 풀이하였으나 풀이 방법은 같지만 더 간결한 방법을 참조하였다.

마이너스를 기준으로 계산해야한다는 말은 즉,

식이 50-40+20+20+20-10+20일 때 50-(40+20+20+20)-(10+20)가 최솟값을 가질 수 있다.

그렇다면 처음부터 -를 기준으로 식을 나누어 받아 [50, 40+20+20+20, 10+20]의 리스트 형태로 받아 첫 식 다음의 식을 빼는 방법으로 문제를 풀이했다.

여기서 고려해야하는 점은 마이너스가 없을 때에는 리스트의 요소는 1개만 들어있게 된다는 점을 이용해서 모두 더한 뒤 출력해주면 된다. 소스코드에서는 리스트의 길이를 이용해 두 번째 요소부터 빼도록 하여 스킵되도록 작성하였다.

마지막으로 마이너스 이후의 수들을 더하여 첫 요소에서 값들을 빼주면 된다.

---

풀이 결과