[백준알고리즘] 1541번: 잃어버린 괄호 -Python

[백준알고리즘] 1541번: 잃어버린 괄호 -Python

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

1541번: 잃어버린 괄호

 

단계별로 풀어보기에서 그리디 알고리즘의 마지막 문제이다.

 

이 문제는 괄호를 '+'와 '-'들 사이에 아무 데나 넣어도 된다는 점이 중요하다.

1+2+3-3+4+5 = 12 이지만 괄호를 다음과 같이 넣으면 결과가 달라진다. 1+2+3-(3+4+5) = -6의 결과가 나온다. 이렇게 되는 이유는 괄호를 추가를 하지만 괄호 사이의 '+'나 '-'연산자가 바뀌지 않기 때문이다.

 

 

이번의 아이디어는 굉장히 간단하다. '-'연산자 뒤의 수가 커지면 된다. 따라서 '-'뒤에 괄호를 치고 다음 '-'연산자가 나오게 되면 그전에 괄호를 닫아주면 된다. 즉, '-'값이 maximum이 되기 위해서 '-'연산자 뒤에 괄호를 치고 괄호 안에는 '+'연산자 밖에 들어가지 못해야한다.

 

 

처음 시도할 때에는 '-'연산자를 split()한 후 eval()이란 함수를 찾아서 풀어봤었다. 그런데 eval()이란 함수가 취약하다는 점을 알게 되어서 global 변수를 적용해서 사용했었다. eval()이 취약한 이유나 안전하게 사용하는 방법은 링크로 걸어두도록 하겠다.

 

https://bluese05.tistory.com/64 

https://mainia.tistory.com/5624

http://lybniz2.sourceforge.net/safeeval.html

 

 

그래서 처음에 시도했던 코드는 다음과 같다.

 

import sys

expression = sys.stdin.readline().split('-')

sum = eval(expression[0], "__builtins__":None}, {})
for exp in expression[1:]:
    sum -= eval(exp, {"__builtins__":None}, {})

print(sum)

 

 

자꾸 처음이라고하는 것은 당연히 실패했기 때문이다.

이유는 문제에 써있는 부분 때문이었다.

 

 

 

하지만 eval()에 "012"같은 것은 들어갈 수 없다.

 

>>> eval("0")
0
>>> eval("0+1")
1
>>> eval("0+01")
Traceback (most recent call last):
  File "<pyshell#14>", line 1, in <module>
    eval("0+01")
  File "<string>", line 1
    0+01
       ^
SyntaxError: invalid token
>>> eval("1+0")
1
>>> eval("1+02")
Traceback (most recent call last):
  File "<pyshell#16>", line 1, in <module>
    eval("1+02")
  File "<string>", line 1
    1+02
       ^
SyntaxError: invalid token
>>> print(02)
SyntaxError: invalid token
>>> print(int(02))
SyntaxError: invalid token
>>> 03
SyntaxError: invalid token
>>> int(03)
SyntaxError: invalid token
>>> 0o3
3
>>> x = 03
SyntaxError: invalid token

 

아무래도 0 다음에 수가 바로 올 수는 없는 것 같다. 0b / 0o / 0x처럼 진수를 정해주는 것이 아닌 바로 오는 수를 0으로 시작하는 수로는 받아들이지 못하는 것 같다.

 

그래서 이것을 사용해서 다시 짰다.

 

>>> int("02")
2

 

 

코드는 다음과 같다.

 

import sys

expression = sys.stdin.readline().split('-')

partial_sum = []
for t in expression:
    temp = list(map(int, t.split('+')))
    partial_sum.append(sum(temp))

total = partial_sum[0]
for psum in partial_sum[1:]:
    total -= psum

print(total)

 

 

 

잘못된 점이나 부족한 점 지적해주시면 감사하겠습니다