[BOJ] 1541 잃어버린 괄호

boj.kr/1541

 

내가 모르겠는 문제 잃어버린 괄호 

이게 왜 정답비율 50퍼가 넘는지 모르겠다 ㅎㅎ..

 

맨 처음에는 프로그래머스에 있는 타겟 넘버와 비슷하다고 생각해서

BFS를 이용하려고 했지만, 잘 되지 않았다. 

 

사실 이 문제는 최소값을 찾는 것이기 때문에

마이너스 기호 이후에 나오는 숫자들을 모두 더한 다음에

마이너스 기호 나오기 전 숫자에서 빼주면 되는 것이다. 

예를 들어서 아래 식에 규칙을 적용시키면

55 + 50 - 40 + 30 - 10

55 + 50 - (40 + 30) - 10 

= 25 이 될 것이고, 

55 - 50 + 40 + 30 - 10

55 - (50 + 40 + 30) - 10

= -75 가 될 것이다! 

 

split을 이용하면 더 쉽게 짤 수 있다. 

 

다른 방법이 있을까 싶어 다른 사람들의 블로그를 방문해봤는데, 

대부분 비슷한 방법으로 한 것 같다! 

StringTokenizer를 이용하거나 Split을 이용하거나의 차이인 것 같다. 

로직은 위의 형광펜을 칠한 부분이 모두 일맥상통하니 위의 방법대로 하면 된다.

맨 처음 숫자를 빼지 않게 주의하면 쉽게 풀 수 있을 것이다.