[BOJ] #1541 잃어버린 괄호 (Python)[BOJ] #1541 Lost Parentheses (Python)
📅
🚀
알고리즘 분류 🔗
수학, 문자열, 그리디 알고리즘, 파싱
🚀
문제 설명 🔗
양수와
+, - 연산자로 이루어진 식이 주어질 때, 괄호를 적절히 쳐서 식의 값을 최소로 만드는 프로그램을 작성하면 됩니다.✅
입력 🔗
첫 줄에 식이 주어집니다. 식은
1 이상 1000000 이하의 양수와 +, - 연산자로 이루어져 있으며, 연산자는 최소 한 개 이상 존재합니다. 식의 길이는 최대 50입니다.50-50+40-30+20-10✅
출력 🔗
테스트 케이스의 결과 중 최소값을 출력합니다.
50-(50+40)-(30+20)-10 = 50 - 50 - 40 - 30 - 20 - 10 = -100
-100
문제 설명
🚀
풀이 🔗
- 식에서
-를 기준으로 나누어 각 덩어리를 구분합니다. - 첫 번째 덩어리는 무조건 더합니다.
- 그 이후 덩어리는 모두 괄호로 묶인다고 생각하고 각각 +로 쪼개서 합산한 뒤 빼기.
- 모든 덩어리를 합산한 결과를 출력합니다.
🚀
코드 - 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)✅
차력쇼 🔗
🖐️
따라하지 마세요. 이런 코드는 작성하지 맙시다. 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("+")]))
🚀
핵심 🔗
기호 이후에 나오는 모든 수는 괄호로 묶어서 한꺼번에 빼야 최소값이 나온다.
- +는 괄호 안에서만 영향을 주고,
- -는 괄호의 시작점이 되므로,
- 첫 - 뒤로는 전부 () 안에 들어간다고 생각하면 됨.
✅
시간 복잡도 🔗
- split('-') → O(N)
- 각 덩어리마다 split('+') → 전체 합쳐서 O(N)
- 각 숫자에 대해 int() 변환 → O(N)
- 합계 계산 → O(N)
최종 시간복잡도: O(N)
🚀
반례 모음(예제 제외) 🔗
1-10+20-30+4050-30+25+5055-50+400-10+20+4010-00020+00030+0002510-20+30-40+50-60+70100-10+5+30+40+100100