[BOJ] #1541 Lost Parentheses (Python)

📅

loading..🐩🐩🐩🐩

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

Algorithm categories 🔗

Mathematics, strings, greedy algorithms, parsing.

Problem description 🔗

Given an expression made up of positive integers and the + and - operators, write a program that places parentheses to minimize its value.

Input 🔗

The expression is provided on the first line.

It consists of positive integers from 1 to 1000000 and the + and - operators, with at least one operator.

The expression has a maximum length of 50.

50-50+40-30+20-10

Output 🔗

Print the minimum possible result for the test case.

50-(50+40)-(30+20)-10 = 50 - 50 - 40 - 30 - 20 - 10 = -100

-100

Problem explanation

Solution 🔗

Split the expression at each - to separate it into groups.
Always add the first group.
Treat each subsequent group as parenthesized: Split it at +, sum its numbers, and subtract the result.
Print the result after processing every group.

Code — Python 🔗

expression = input().strip()
 
  # 1. '-'를 기준으로 먼저 나눈다.
parts = expression.split('-')
 
  # 2. 첫 번째 덩어리는 무조건 더한다.
total = sum(map(int, parts[0].split('+')))
 
  # 3. 그 이후 덩어리는 모두 괄호로 묶인다고 생각하고 각각 +로 쪼개서 합산한 뒤 빼기
for part in parts[1:]:
    total -= sum(map(int, part.split('+')))
 
print(total)

A coding stunt 🔗

🖐️

Do not copy this. Let's avoid writing code like this.

line = input().strip().split("-")
answer = sum(list(map(int, line[0].split("+"))))
print(answer if len(line) <= 1 else answer - sum([list(map(int, s.split("-")))[0] for s in "+".join(line[1:]).split("+")]))

Key points 🔗

To get the minimum value, group all numbers following the subtraction sign into parentheses and subtract them together.

- only affects the sum inside a group.
- marks the start of a group.
Think of everything after the first - as belonging inside ().

Time complexity 🔗

split('-') → O(N).
split('+') for each group → O(N) in total.
Converting each number with int() → O(N).
Calculating the total → O(N).

Overall time complexity: O(N).

Additional test cases, excluding the examples 🔗

answer: -99

1-10+20-30+40

answer: -55

50-30+25+50

answer: -35

55-50+40

answer: -70

0-10+20+40

answer: -65

10-00020+00030+00025

answer: -260

10-20+30-40+50-60+70

answer: -85

100-10+5+30+40+100

answer: 100

[BOJ] #1541 Lost Parentheses (Python) | PromleeBlog