[python] 백준 1541 - 잃어버린 괄호 / 그리디 알고리즘 /구현을 중심으로 ( 구현 아이디어를 다시보자 )/ (스터디 공개)

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

1541번: 잃어버린 괄호

 

문제를 딱 읽자마자 그리디 알고리즘이라는 생각이 든다. 

문제는 구현 방식에 있었다. 

expression=input()
num_list = []
plus_and_minus = []
now =''
for i in expression:
    if i == '+' or i =="-":
        plus_and_minus.append(i)
        num_list.append(int(now))
        now =''
    else:
        now += '{}'.format(i)

num_list.append(int(now))


plus = True
sum = num_list[0]
index = 0

for num   in num_list[1:]   :
    if plus == True and plus_and_minus[index] =="+":
        sum += num 
    
    elif plus == True and plus_and_minus[index]=="-":
        sum -=num 
        plus =False
    
    elif plus == False and plus_and_minus[index] =="+":
        sum -= num
    
    elif plus == False and plus_and_minus[index] =="-":
        sum -=num
    index += 1

print(sum)

뭐랄까.. 그냥 문제를 내가 이해한 방식 ( 사람의 방식으로..) 어떻게 해야 풀 수 있을지만 고민한 코드같다. 

다음단계로 넘어가기 위해서는 조금 더 기계스러운(?) 방식으로 문제를 해결 했으면 좋겠다. 스스로한테도 조금 답답한 풀이였고 분명히 풀면서 이거보다 좋은 풀이가 있을거 같은데.... 라는 생각이 끊이지 않았다. ( 다른 풀이들과 시간의 차이는 없었지만 숏코딩에서 엄청나게 차이가 났고 배울점들이 많았다.) 

 

내가 푼 풀이는 - 기호가 나오고부터 뒤에숫자들을 총합에다가 빼면되는 식이였다. 그런데 사실 문제 이름 자체에서도 보듯이 '잃어버린 괄호' 에 중점을 둔다면 어떤식으로 괄호를 치면 좋을까? 생각해보면 좋겠다. 

 

 

https://pacific-ocean.tistory.com/228

a = input().split('-')
num = []
for i in a:
    cnt = 0
    s = i.split('+')
    for j in s:
        cnt += int(j)
    num.append(cnt)
n = num[0]
for i in range(1, len(num)):
    n -= num[i]
print(n)

 

위의 블로그에서 따온 코드이다. 대부분 코드들이 이런식인데 '괄호'를 치기 위해서 -를 기준으로 문자열을 슬라이싱해준다. 

그렇게 된다면 예제에서

55 -50 + 40 +60 -20 이런식으로 입력 받았다면 

55 / 50+40+60 / 20  이런식으로 슬라이싱 될 것이다. 

이렇게 입력을 받은뒤에 해결 해주면 된다. 

 

저번 문제에서는 하나의 딕셔너리로 입력값을 받으려다가 고생했는데 이번에는 오히려 '숫자' 와 '기호' 를 따로 나누려다보니 사고가 좀 좁아진 것 같다. 처음 문제를 설계할때 시간을 조금더 쓰면 구현을 쉽게할수 있는 ( 머리가 좋으면 몸이 고생을 덜하듯이..). 아직도 구현부분에서 남들만큼 잘하는거 같지 않다. 특히 코드들을 너무 무겁게 짠다는 느낌이 스스로도 체감이 된다. 어떻게 고치면 좋을지 참 난감하다. 

이럴때일수록 남들의 코드를 참고해서 보고 내것으로 체화해보는 것이 좋겠다. 

 

 

 

 

 

 

+) 

훨씬더 숏코딩한 코드들이다 

a,*b=[sum(map(int,x.split("+")))for x in input().split("-")];print(a-sum(b))

패킹/언패킹을 이용해서 더 파이써닉하게 문제를 풀었다. 나는 언제쯤 이정도 레벨이 될런지...