[Python] 백준/BOJ 1541번: 잃어버린 괄호 (Silver 2)

💻 Problem

문제 보러 가기

 

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

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

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

 

💡 Approach

처음에 생각이 잘 안 났다..

그리디인 줄도 몰랐는데 모든 경우의 수를 따지는 게 아니라 괄호가 들어가야 하는 최선의 선택만을 따져야 해서 그리디인 것 같다.

 

문제의 목표는 식의 값을 최소로 만드는 것이다.

식의 값을 가장 작게 만들기 위해서는 최대한 큰 수를 빼야 한다.

즉, '-' 뒤에는 항상 괄호를 치는 것이 좋다.

 

예를 들어, 5+4-5-10+20 라는 식이 주어졌다고 치자.

가장 작은 수를 만들기 위해서는 빼는 수가 최대한 커야 한다.

5+4-5-10+20 여기서 그냥 -10을 하는 것보다 -(10+20)을 하면 빼는 값이 더 커진다.

 

'-' 뒤에는 괄호를 친다고 생각하고 '-'를 기준으로 처음 식을 쪼갠다.

쪼갠 식은 5+4, 5, 10+20 일 것이다.

 

각각의 쪼갠 식들을 계산한다.

마찬가지로 각각의 식을 '+'를 기준으로 쪼개서 더하면 된다.

그러면 9, 5, 30이 된다.

 

마지막으로 9-5-30을 구하면 최소 결괏값인 -26이 나온다.

 

✏️ Solution

import sys
input = sys.stdin.readline

# '-'를 기준으로 식을 쪼갠다
exprs = input().rstrip().split('-')
num = []

# 쪼갠 식들을 각각 계산한다
# '+'를 기준으로 다시 쪼개서 합을 구한다
for expr in exprs:
    num.append(sum(map(int, expr.split('+'))))

# num 리스트 안의 숫자들을 계산한다
# num[0] - num[1] - ...
ans = num[0]
for i in range(1, len(num)):
    ans -= num[i]

print(ans)

 

시간복잡도는 O(n)이다.

 

추가로 위 코드를 더 짧게 압축할 수 있다..!

내용은 같지만 더 짧게 쓴 코드이다.

 

import sys
input = sys.stdin.readline

# 입력받은 식을 '-'로 쪼갠다
exprs = input().rstrip().split('-')

# '+'를 기준으로 다시 쪼개서 합을 구한다
num = [sum(map(int, expr.split('+'))) for expr in exprs]

# num 리스트 안의 숫자들을 뺀다
ans = num[0] - sum(num[1:])

print(ans)

 

네 줄 컷.. 파이썬은 놀라워🙄