[백준] 1541 잃어버린 괄호

Hyun·2024년 3월 9일

greedy 백준

백준

목록 보기

36/81

문제

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

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

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

입력

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

출력

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

예제 입력

55-50+40

예제 출력

-35

풀이

간단하게 보이는 문제라도 쉽게 푸는 방법은 생각하기 힘든 것 같다.

문제를 푸는 방법은 대표적으로 2개가 있다(고 생각한다)

첫번째(실패)

괄호를 직접 추가하여 파이썬의 eval 함수를 사용해 식의 결과를 출력시키기

방법
닫힌 상태라면 '-' 뒤에 여는 괄호 '(' 를 추가하고, 열린 상태라면 '-' 앞에 닫는 괄호를 추가해주면 된다.

이 방법은 괄호를 추가하기 전에 미리 숫자로 표현된 값들을 정수형으로 바꾸는 과정을 거쳐야 한다. (ex 00009 -> 9) , 이 방법은 복잡하며, 직관적이지 않다.

또 문제가 있는데 이렇게 괄호를 insert 하게 되면 직전에 '-' 를 만났음에도 닫는 괄호 ')' 를 만나면 다시 또 만나게 되는 문제가 발생한다..

st = input()

# ---------- 정수형으로 바꿔주기 ----------- # 
# 먼저 - 로 쪼개기
f_minus_list = st.split("-")
print(f_minus_list)
# 그다음 + 로 쪼개기
for i in range(len(f_minus_list)):
    f_plus_list = f_minus_list[i].split("+")
    # + 로 쪼갠 원소들 int형으로 다 바꾸기
    for j in range(len(f_plus_list)):
        f_plus_list[j] = str(int(f_plus_list[j]))
    # 다시 + 로 합치기
    f_minus_list[i] = "+".join(f_plus_list)

# 다시 - 로 합치기
f = "-".join(f_minus_list)
f_lst = list(f)

# ----------- 괄호 붙히기 ----------- #
# 괄호 닫힌 상태 & - 만남 => - 뒤에 괄호 열기
# 괄호 열린 상태 & - 만남 => - 앞에 괄호 닫기
isClosed = True
for i in range(len(f_lst)):
    if f_lst[i] == "-":
        if isClosed is True: f_lst.insert(i+1, "(")
        else: f_lst.insert(i, ")")
        isClosed = not isClosed
if isClosed is False: f_lst.append(")")
f = "".join(f_lst)
print(eval(f))

두번째

괄호를 직접 추가하지 않고, - 와, + 를 기준으로 split() 함수를 사용하여 풀이한다.

방법
'-' 로 쪼개진 값들 중 첫번째 값(식)에 있는 값들을 '+' 로 쪼갠 값들을 모두 더해 시작 값으로 두고, 나머지 값(식)들을 '+' 로 쪼갠 값들을 시작 값에서 모두 빼주면 된다.

'-'로 쪼개진 값들중 첫번째 값(식)을 먼저 계산하여 시작값으로 사용하는 이유는, 유일하게 뺄셈이 아닌 덧셈이 필요한 값(식)이기 때문이다.

f = input()
f_minus = f.split("-")
total = 0
for val in f_minus[0].split("+"):
    total += int(val)

for lst in f_minus[1:]:
    for val in lst.split("+"):
        total -= int(val)

print(total)