[백준] 1541번 잃어버린 괄호 Python 해설 (그리디 알고리즘)

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

1541번: 잃어버린 괄호

그리디 알고리즘으로 분류된 문제이다.

코딩 테스트나 알고리즘 경진대회에서 해당 알고리즘이 나온다면 확실하게 점수를 가져가야 한다!!

그리 어렵지 않은 알고리즘이니 쉽게 문제를 풀어보자

 

풀이

---

여기에 그리디 알고리즘에 대해서 언급한 적이 있다.

간단하게 가장 좋은 선택을 알고리즘이라고 생각한다.

 

"잃어버린 괄호" 문제는  가장 최소의 결과를 얻는 괄호를 쳐서 최소의 결과를 얻어내야 한다.

마이너스를 만날 때 가장 큰 수를 빼면 되는 것이다.

마이너스 기호를 만날 때 다음 마이너스 까지, 다음 마이너스가 없다면 끝까지 모든 수를 더해서 한 번에 빼 주면 문제에서 원하는 답을 얻을 수 있다.

 

이렇게 말로는 쉽지만 나도 네 번이나 틀렸다. 마이너스가 없을 때를 고려하지 않는 실수를 저질렀다.

실제 코딩 테스트였으면 멘탈이 엄청 흔들렸을 것 같다.

 

- 정답 코드

arr = input().split('-')
s = 0
for i in arr[0].split('+'):
    s += int(i)
for i in arr[1:]:
    for j in i.split('+'):
        s -= int(j)
print(s)

 

 

 

결과

---

항상 사소한 실수를 조심하고 제출하기 전까지 신중하게 풀자!