[백준] 1541 잃어버린 괄호 (Python 파이썬)

www.acmicpc.net/problem/1541

1541번: 잃어버린 괄호

문제 설명

수식이 문자열로 주어질 때, 적절한 괄호를 쳐서 수식의 결과값을 최소로 만들면 된다.

단, 처음과 숫자는 숫자이며, 두 개 이상의 연산자가 나타나지 않으며(++,--) 연산자는 +, -만 사용할 수 있다.

---

풀이 과정

그리디 알고리즘 문제이다. 최소값을 만들기 위해선 어떻게 해야할까?

마이너스 바로 뒤에 괄호를 열고 그 안의 수식을 최대로 만든 후 다시 괄호를 닫으면 된다.

처음 풀었던 방법은 바로 아래의 코드인데, 마이너스를 만나면 즉시 괄호를 열고, 그 뒤의 마이너스를 만나면 다시 괄호를 닫는 식으로 하여 해결하였다. 그리고 결과값을 eval함수를 이용하여 출력하였다.

 

정답은 정상적으로 잘 출력되었지만 백준에서 정답을 돌렸을 때, Syntax Error가 발생하였다.

왜냐하면 eval함수안에서 1,3,5등 일반적인 숫자는 잘 인식하지만 01, 001등 앞에 0이 붙은 수는 인식하지 못한다.

그래서 에러가 발생하였다. (문제에서 수는 0으로 시작할 수 있다고 하였음)

exp = input()
ans = ''

flag = 0 # 괄호 열기전
for i in range(len(exp)):
    if exp[i] == '-':
        if flag == 0:
            ans += exp[i]
            ans += "("
            flag = 1
        else:
            ans += ")"
            ans += exp[i]
            ans += "("
    else:
        ans += exp[i]

if flag == 1:
    ans += ")"
print(ans)
print(eval(ans))

 

그래서 다른 방법을 고안하였고, 코드는 다음과 같다.

먼저 -를 기준으로 문자열을 분리해 준다. 이렇게 되면 첫번째 인덱스를 제외한 각각의 분리된 수식의 앞에는 -가 붙는다는 이야기가 된다.

그래서 첫번째 인덱스의 숫자만 더해주고 나머지 인덱스의 수들은 모두 빼주었다.

이렇게 해서 Syntax Error없이 통과할 수 있었다.

exp = input().split("-")
ans = 0
for i in exp[0].split("+"):
    ans += int(i)

for i in exp[1:]:
    for j in i.split("+"):
        ans -= int(j)

print(ans)

https://github.com/HongEunho

HongEunho - Overview

전체 문제 & 코드는 위의 깃에 정리되어 있습니다.

팔로우 & 맞팔은 환영입니다 !