그리디 알고리즘 연습하기2 -잃어버린 괄호-

1. 문제

 

1541번: 잃어버린 괄호 (acmicpc.net)

1541번: 잃어버린 괄호

 

수식에 괄호를 쳐서 결과를 최소로 만드는 문제

 

 

2. 풀이

 

수식에 +,-만 나온다는 점을 생각하면..

 

이 수식이 최소가 될려면??

 

+를 먼저 계산해서, 각 항을 최대로 만들어줘야한다.

 

그래야 -에 의해 최소가 되겠지

 

그래서 -로 수식을 split해주고...

 

split된 리스트를 순회해서... 각 원소를 int()로 바꿔본다.

 

int()로 바꿀때 에러가 나거나 나지 않거나 둘중 하나다.

 

에러가 나지 않으면 minus라는 리스트에 일단 넣어준다.

 

try: except로 처리하자

 

에러가 나면 그 원소에는 +가 포함되어 있다는 뜻이다

 

그러므로, 에러가 나는 경우, +로 split한다음에 각 항을 모두 더해준다.

 

더한값을 minus라는 리스트에 넣어준다.

 

모든 리스트를 순회했다면, +부분은 전부 계산한것이다.

 

그러한 계산결과가 minus에 들어가있고, 0번째 원소에, 1번~마지막 원소까지 순회하면서 빼주면 될것

 

from sys import stdin

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

minus = []

for e in expression:
    
    try:
        
        e = int(e)

        minus.append(e)

    except:
        
        plus = e.split('+')

        temp = 0

        for e in plus:
            
            temp += int(e)
        
        minus.append(temp)

answer = minus[0]

for m in minus[1:]:
    
    answer -= m

print(answer)

 

처음볼땐 어렵다고 생각했는데 생각보다 잘 풀었네...

 

연습의 효과인가?