[백준] 1541번 잃어버린 괄호 해설 및 풀이 (Python)

 

백준 1541 잃어버린 괄호

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

 

 

---

문제

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

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

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

입력

첫째 줄에 식이 주어진다. 식은 ‘0’~‘9’, ‘+’, 그리고 ‘-’만으로 이루어져 있고, 가장 처음과 마지막 문자는 숫자이다. 그리고 연속해서 두 개 이상의 연산자가 나타나지 않고, 5자리보다 많이 연속되는 숫자는 없다. 수는 0으로 시작할 수 있다. 입력으로 주어지는 식의 길이는 50보다 작거나 같다.

출력

첫째 줄에 정답을 출력한다.

 

---

 

문제 풀이

 

 

문제 유형

수학

그리디 알고리즘

문자열

파싱

 

 

풀이 방법 도출 과정

 

주어진 수식을 최소값으로 만드는 방법을 찾아야 합니다.

+와 -만 존재하는 수식에서 최소값을 만들려면 - 연산자를 기준으로 괄호를 넣으면 됩니다.

 

예를 들어, 55-50+40의 경우 55-(50+40)으로 괄호를 치면 -35가 됩니다.

 

따라서 문제를 해결하는 방법은 이렇습니다.

 

1. 우선 마이너스(-)를 기준으로 수식을 분리합니다.
2. 맨 처음 등장하는 마이너스(-) 이후의 모든 숫자는 한 번에 묶어서 뺍니다.
3. 마이너스(-)를 만나기 전까지는 더하면 됩니다.

 

이와 같이 코드로 구현하는 방법은 이렇습니다.

 

1. 문자열을 하나씩 읽으면서 숫자 num에 저장합니다.
2. 플러스(+) 또는 마이너스(-) 연산자를 만나면 그때까지 저장한 숫자를 result에 반영합니다.
3. 마이너스(-) 연산자가 나타나면 이후 숫자는 모두 빼도록 minus 변수를 True로 설정합니다.

 

 

시간 복잡도

 

O(N)

 

---

 

문제 풀이 코드

 

import sys


# 빠른 입력 사용
input = sys.stdin.readline


# 앞뒤 공백을 제거
expression = input().strip()


# 결과 값
result = 0
# 숫자
num = ''
# '-' 기호가 등장했는지 여부를 판단하는 변수
minus = False


# 수식을 처음부터 끝까지
for char in expression:
    if char.isdigit():  # 현재 문자가 숫자라면
        num += char  # 숫자를 문자열로 계속 이어 붙임
    else:  # 연산자를 만난 경우
        if minus:  # 이전에 '-'가 등장한 경우, 현재 숫자를 빼야 함
            result -= int(num)
        else:  # 그렇지 않다면 더함
            result += int(num)
        num = ''  # 숫자 초기화


        if char == '-':  # '-' 연산자를 만나면 이후의 숫자들은 모두 빼야 함
            minus = True


# 마지막 숫자를 결과에 반영
if minus:
    result -= int(num)
else:
    result += int(num)


# 최종 결과 출력
print(result)