[그리디] 백준 #1541 잃어버린 괄호 - Python

🗂️ 문제

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

1541번: 잃어버린 괄호

 

💡 접근법

그리디 알고리즘을 사용한다.

최소값을 구하기 위해서는 작은 수에서 큰 수를 빼야 한다. 따라서 덧셈으로 연속된 부분에 괄호를 쳐서 이를 계산한 후 빼는 방식으로 문제를 해결하면 된다.

 

이때 예외처리로 주의해야 할 부분이 있다.

 

-로 입력값을 split하고 문제에서 주어진 테케를 시도할 경우 A = ['100', '40+50+74', '30+29', '45+43+11']이다. 이때 A[0] = 100을 초기값으로 두고 초기값에서 이후 덧셈으로 이루어진 부분을 빼는 방식으로 구현할 경우엔 문제가 없다.

하지만 A = ['100+50', '40+50+74', '30+29', '45+43+11']일 경우에는 A[0] = 100+50에서 뺄셈을 수행할 수 없다.

 

따라서 아래 코드와 같이 덧셈으로 이루어진 값들을 모두 계산해서 저장하는 cal 리스트를 따로 선언하고, cal[0]을 초기값으로 한 뒤 cal[0] 이후 값들에 하나씩 접근하여 뺄셈을 수행해야 한다.

 

😎 내 코드

import sys

A = list(sys.stdin.readline().rstrip().split('-'))

cal = []
for i in range(len(A)): # 덧셈으로 이루어진 식을 계산하여 cal에 저장
    result = 0
    temp = list(A[i].split('+'))
    for t in temp:
        result += int(t)
    cal.append(result)

ans = cal[0] # cal[0]을 초기 값으로 지정
for i in range(1, len(cal)): # cal[1]부터 순차적으로 뺄셈 수행
    ans -= cal[i]

print(ans)

 

✅ 정답 확인