(C++) 백준 1541번 잃어버린 괄호

1. 문제 

www.acmicpc.net/problem/1541

1541번: 잃어버린 괄호

 

2. 필요한 개념

문제의 핵심은 +과 -만 존재한다는 것이다. 

즉 식의 우선순위가 없으므로 괄호 내부에서도 앞에서부터 식이 진행된다. 

따라서 - 뒤에 괄호를 시작해서 그 다음 -앞에서 괄호를 닫아주면 된다. 

예를 들면 

50 + 20 + 30 - 49 +66 - 80 식이 있다 하면

50 + 20 +30 - (49 +66)- 80 이렇게 바꿀 수 있다는 것이고 이는

50 + 20 + 30 -49 - 66 -80 이 된다. 

 

즉 - 가 한번이라도 나오면, 그 뒤는 모두 -로 바뀔 수 있는 것이다. 

이를 이용하여 나는 bool isminus = false 로 두고 -가 한번이라도 나오면 이를 true로 바꾸어 이후 수를 모두 ans 에서 빼주었다 

 

문제는 c++ 에서 스트링을 split 하는게 굉장히 복잡하다는 것이다.. 

심지어 이 문제 같은 경우 구분자가 '+' , '-' 두개로 더 복잡하다. 

 

따라서 내가 택한 방법은 substr함수를 사용하여 구분자가 나올 때마다 문자열을 잘라 또다른 배열에 저장하는 방식이다.

 

3. 소스 코드

github.com/gimkuku/Algorithm/blob/master/Greedy/1541.cpp