[백준] 1541번 - 잃어버린 괄호

문제 설명

세준이는 양수와 +, -, 그리고 괄호를 가지고 식을 만들었다. 그런데 세준이는 실수로 모든 괄호를 지워버렸다.
이제 세준이는 괄호를 적절히 배치하여 식의 결과를 최소로 만들고 싶어 한다.

세준이를 도와 괄호를 적절히 배치했을 때, 식의 최소값을 구하는 프로그램을 작성하자.

입력

• 첫째 줄에 식이 주어진다.
• 식은 0-9, +, - 로 이루어져 있으며, 처음과 마지막 문자는 숫자이다.
• 연속해서 두 개 이상의 연산자가 나타나지 않으며, 숫자는 최대 5자리이다.
• 입력 식의 길이는 50 이하이다.

출력

• 첫째 줄에 괄호를 적절히 배치하여 얻을 수 있는 최소값을 출력한다.

---

풀이 방법

이 문제는 그리디 알고리즘(Greedy Algorithm) 을 활용하여 해결할 수 있다.
핵심 아이디어는 -를 기준으로 분할하여, 이후의 모든 수를 묶어 최대한 크게 만든 후 빼는 것이다.

1. 내가 처음 접근한 방법

처음에는 오른쪽에서 왼쪽으로 탐색하면서, +, - 연산자를 처리하여 계산하는 방식을 생각했다.

expr = input()

total = 0
sub_total = 0
target = ''

for i in range(len(expr) - 1, -1, -1):
    if expr[i] in ('+', '-'):
        sub_total += int(target)
        target = ''

        if expr[i] == '-':
            total += -sub_total
            sub_total = 0
    else:
        target = expr[i] + target

total += sub_total + int(target)
print(total)

🔹 문제점

• 문자열을 직접 파싱하면서 연산을 수행했기 때문에 가독성이 떨어진다.
• -가 등장할 때마다 sub_total을 초기화하면서 관리하는 방식이 직관적이지 않다.
• 문제에서 요구하는 최적의 괄호 배치 아이디어를 적극 활용하지 못했다.

---

2. - 기호를 기준으로 분할하는 방법

이 문제의 핵심은 첫 번째 - 기호가 등장한 이후부터는 모든 수를 더한 후 한꺼번에 빼버리는 것이다.
즉, -를 기준으로 문자열을 나누고,

• 첫 번째 부분은 모두 더하고
• 이후 부분은 각각의 수를 더한 후 한꺼번에 빼주면 된다.

🔹 개선된 코드

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

# 첫 번째 덩어리는 그대로 더함
total = sum(map(int, expr[0].split('+')))

# 이후의 덩어리는 모두 더한 후 빼기
for sub in expr[1:]:
    total -= sum(map(int, sub.split('+')))

print(total)

🔹 코드 설명

1. - 기호를 기준으로 문자열을 분할하여 리스트 expr을 만든다.
2. expr[0]은 처음에 그대로 더하고, 이후부터는 - 기호가 있으므로 각 덩어리를 더한 후 한꺼번에 빼준다.
3. map(int, sub.split('+'))을 사용하여 + 연산이 포함된 부분을 먼저 계산한 후 total에서 빼준다.

---

시간 복잡도 분석

접근 방식	시간 복잡도	이유
기존 코드	O(N)	문자열을 직접 탐색하며 연산 수행
개선된 코드	O(N)	문자열을 한 번 나누고, 연산 수행

---

✨ 핵심 정리

• - 기호를 기준으로 괄호를 쳐야 할 곳을 결정한다.
• 첫 번째 - 이후의 모든 값을 더한 후 한꺼번에 빼면 최솟값을 얻을 수 있다.
• split('-')을 이용해 리스트로 나누고, 첫 번째 부분은 더하고, 이후 부분은 합산 후 빼는 방식으로 해결하면 쉽다.
• 그리디 알고리즘을 활용하여 최적의 선택을 반복적으로 수행한다.