백준 1541 잃어버린 괄호

❌ 백준 1541 잃어버린 괄호

오답.

풀이방법이 도저히 생각나지 않아서 알고리즘 카테고리를 확인했다.

그리디 알고리즘이라는데 처음보는 개념이었다.

구글링해서 어떤 개념인지는 알았는데, 이 문제에 어떻게 응용할지 감이 오지 않았다.

결국 다른 사람의 풀이를 확인했다.

최솟값이 되려면 결국엔 다음 마이너스가 나오기 전까진 값들을 더해서 마이너스 되는 수를 최대로 해줘야 한다. 이것만 아니까 풀이는 쉬웠다.

예시) 53+7-30+5+30-10+3

3번 행
:
처음으로 입력받은 문자열을 -기준으로 나눠준다.

['53+7', '30+5+30', '10+3']

이렇게 하면 마이너스 되는 값이 최대가 되도록 괄호를 친 효과를 얻을 수 있다.

5번 행
:
+가 포함된 문자열의 계산을 해주기 위해 for문을 썼다.
만약 +가 문자열에 포함되어있으면 +기준으로 나눠서 전부 합해주고, 같은 index에 결과값을 넣어준다.

13번 행
:
예외처리 부분이다.
값 배열이 하나밖에 없으면 그냥 바로 출력하고 끝낸다.
두개 이상이면 첫번째 결과에서 나머지를 다 마이너스한다.
그리고 결과값을 출력한다.

import sys

mystr = sys.stdin.readline().rstrip().split('-')

for idx,i in enumerate(mystr):
    if '+' in i :
        plusArr = i.split('+')
        result = 0
        for x in plusArr :
            result+=int(x)
        mystr[idx] = result

if len(mystr) == 1 :
    print(mystr[0])
    quit()
else :
    fin_result = int(mystr.pop(0))
    for idx in range(len(mystr)) :
        fin_result -= int(mystr.pop(0))
    print(fin_result)