개발 공부
[BOJ] 1541 잃어버린 괄호
심지두리
2019. 6. 8. 22:33
내가 모르겠는 문제 잃어버린 괄호
이게 왜 정답비율 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을 이용하거나의 차이인 것 같다.
로직은 위의 형광펜을 칠한 부분이 모두 일맥상통하니 위의 방법대로 하면 된다.
맨 처음 숫자를 빼지 않게 주의하면 쉽게 풀 수 있을 것이다.