[백준] 잃어버린 괄호 - Python

Juppi·2022년 5월 23일
0

Algorithm

목록 보기
4/4

"잃어버린 괄호" 주어진 식에 괄호를 적절하게 삽입하여, 계산된 식이 최솟값이 되도록 만드는 문제이다. 입력으로 한줄짜리 식이 주어지며, 숫자는 앞에 0이 붙어서 "0009" 처럼 입력될 수도 있기 때문에 해당 문자열 처리까지 고려해야한다.

문제 접근

주어진 식이 최솟값이 되도록 하려면, 큰 수를 빼주면 된다 !

그러므로 아래 그림의 두번째 수식처럼 + 주변에 괄호를 쳐서, + 먼저 계산하는 것으로 문제를 해결하면 된다. 괄호만 잘 삽입된다면, 수식자체는 eval 같은 함수를 사용하거나, 그대로 계산해주면된다.

eval() 함수를 사용할 경우에는, 예제 3번같은 수식을 바로 계산할 수 없다.
eval("00009-00009")를 해보면 에러가나는 것을 볼 수 있는데, 10진수에서는 0으로 시작하는 숫자를 사용하지 않기때문에 나는 에러라서 "9-9"로 바꿔줘야한다 !

어려웠던 점

문제 접근까지는 어렵지않았으나,, 괄호를 적절하게 삽입하는 부분에서 문제가 발생했다.
반복문으로 수식의 문자 하나하나 돌면서 "+"를 만나면 양 옆 숫자에 괄호를 삽입하는 식으로 코드를 짰는데, 삽입하고나서 보면 서로 다른부분의 괄호가 겹칠 때가 있어서 생각보다 구현문제가 복잡해지는 것이다. (물론 아직 코딩실력이 부족해서 그런듯 ㅠㅠ)

좀 더 쉽게 풀 수 있는 방법이 없나 생각하던 도중, 파이썬의 split() 함수가 생각났다.
"-" 를 기준으로 나누면, 자연스럽게 ["20+40", "50+10", "70"] 처럼 덧셈 관련 수식만 남고, 이 수식들을 먼저 계산한 다음 차례대로 빼주면 해결된다.

아래는 최종 구현 코드이다.

완성된 코드

Python

origin = input()

equation = ""
stack = ""

# 0으로 시작하는 숫자의 0을 제거하는 과정
for i in origin:
  if 48 <= ord(i) and ord(i) <= 57:
    stack += i
  else:
    equation += str(int(stack))
    equation +=i
    stack = ""
else:
  equation += str(int(stack))

# +주변에 괄호를 치는 효과
equation = equation.split("-")

answer = eval(equation[0])*2
for i in equation:
  answer -= eval(i)

print(answer)

    

문제 링크

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

profile
잠자면서 돈버는 그날까지

0개의 댓글