[백준/파이썬] 1541 : 잃어버린 괄호

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

1541번: 잃어버린 괄호

문제 요약 : 주어진 식을 괄호를 적절히 사용하여 최소 값을 구한다.

solved.ac를 보니 너무 DP랑 graphs만 풀었나 싶어서 greedy도전,,

 

시도 1 )

처음에 괄호를 여러개 쓸 수 있는 것을 간과해서 괄호를 어디서 끝내야하는지 고민하느라 시간을 너무 많이 써버렸다..ㅜ

 

괄호 개수의 제한이 없기 때문에 -값이 커질 수 있게 다 괄호로 만들었다.

3 - 5 + 7 - 9 + 15

라고 하면

3 - ( 5 + 7 ) - ( 9 + 15 ) 가 최소 값이 된다.

cal = '('+input()+')'
cal = cal.replace('-',')-(')
print(eval(cal))

신나서 케이스도 다 안돌려보고 제출.. 몽총...

런타임에러가 떴다 당연함 이 문제에서는 숫자가 0으로 시작하는 것을 허용해줬기 때문이다.

 

eval은 0009 + 0009 같이 0으로 시작하는 숫자를 계산해주지 못한다

그래서 0009같은 케이스를 9로 바꾸는 것에 집중했다

 

시도 2 )

입력받은 값에서 부호를 제외한 숫자들을 tmp값에 저장하여 int로 바꿔준 다음 str로 다시 변환해서 final값에 합쳐주었다

코드를 짜면서도 비효율적이라고 느껴졌다

아마 0을 없애는 데에만 집중해서 그런듯..

import sys
input = sys.stdin.readline

cal = input()
tmp = ''
final = ''

for i in range(len(cal)):
    if cal[i] == '-' or cal[i] == '+' :
        final+=str(int(tmp))+cal[i]
        tmp = ''
        continue
    else :
        tmp+=cal[i]
        
final+=str(int(tmp))
final = '('+final.replace('-',')-(')+')'

print(eval(final))

돌아가긴 돌아갔지만 찝찝한 코드,,

 

시도 3 )

괄호 넣기

eval로 계산하기

이거 두개에 집착하다보니 저런 결과가 나온 것 같았다

 

실상 괄호 넣을 필요도 eval로 할필요도 없이 -를 기준으로 입력값을 나눠준다음, + 연산을 하고 빼주면 되는 거였음

 

입력값을 split으로 두번 나눠주는 것까지는 생각했는데 그 값들을 저장하는 것에 버벅거렸다

map을 모르는 것도 아닌데 평소 너무 입력값을 받아올 때 쓰는걸로 머리속에 고정이 되어 버렸는지

생각하는데에 꽤 시간이 걸렸다 T_T

 

cal[0]값은 무조건 더해줘야하기 때문에 앞에 따로 빼주고 나머지 값들은 더한다음 뺄 수 있도록 for문을 돌렸다

import sys
input = sys.stdin.readline

cal = input().split('-')
ans = sum(map(int,cal[0].split('+')))

for i in cal[1:]:
    ans -= sum(map(int,i.split('+')))

print(ans)

이게 더 좋은 코드겠거니 했는데 시간이나 메모리나 똑같았음...🥺

 

다른 분의 코드를 봤는데 나와 거의 유사하지만 sum(map)이 아닌 for문을 돌린 것을 알게 되었다.

for문이 더 오래 걸리지 않을까 했는데 아니였음,, 아직 많이 공부가 필요한것같당 아자아자 화이팅...