[백준] 1541번 : 잃어버린 괄호(탐욕 알고리즘)- 파이썬[Python]

choisanghyun 2022. 1. 18. 00:02

728x90

문제

1541번: 잃어버린 괄호

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

www.acmicpc.net

풀이

n=input().split('-')

list1=[]
for i in range(len(n)):
  n2=list(map(int,n[i].split('+')))
  list1.append(sum(n2))
solve=list1[0]
for i in range(1,len(list1)):
  solve-=list1[i]

print(solve)

문자열 파싱하는 것이 중요한 문제이다.

우선 split('-')으로 문자열을 자르고 리스트를 확인하면, 어떤 식으로 풀어야할 지 감이 잡힌다.

괄호를 임의로 넣어서 최소값이 나오게 하려면 '-'연산자 이후의 '+'연산자 들을 묶어주면 된다.

'-'를 기준으로 파싱하면 첫 숫자를 제외한 '+'연산자 들만 모이게 되는데 이를 sum으로 합해주고

첫 숫자에서 차례로 빼주면 된다.