[백준 | 파이썬3] 1541. 잃어버린 괄호- 그리디알고리즘

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

1541번: 잃어버린 괄호

> 그리디

괄호를 추가하여 식의 결과를 '최소'로 만드는 알고리즘을 구현해야한다. 

 

'-' 이전의 수들은 모두 더해주고 '-' 이후의 수들을 모두 빼주면 최소 값을 구할 수 있다.

예를 들어, 

1+2-3+4-5 에서 '-' 는 두번 나온다. 우선 이 두개를 기준으로 괄호를 넣어주면 다음과 같이 표현된다.  

1+2-(3+4)-(5)

그런데 위의 식은 사실상 아래의 식과 같다. 

(1+2)-(3+4+5)

따라서 처음 나오는 '-'를 기준으로 앞의 숫자들을 모두 더한 것과 뒤의 숫자를 모두 더한 값을 빼주면 최소 값이 나온다. 

 

위 아이디어를 코드로 구현한 것이다. 

 

 

> 배운 점

다른 사람들의 풀이를 보니 시간복잡도가 덜한 코드에선 '-'를 기준으로 다음 식과 같이 모두 분리한 후 '+'를 기준으로 다시 분리한 수들을 모두 더해준 후, 

(1+2)-(3+4)-(5)

마지막에 (1+2)와 '-' 뒤의 모든 요소들의 합을 빼주는 방식으로 작성했다.

이 방식으로 하면 굳이 문자열 식에서 숫자를 골라내는 부분을 넣지 않아도 된다.

 

리스트 컴프리헨션을 사용하여 해당 방식대로 구현하면 52ms 가 걸린다.