Lets go show

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

처음에 문제를 천천히 읽어 보면서 이 문제의 특징을 먼저 파악해 보려고 했다.
1. 연산자의 우선순위가 없다.
2. 중첩 괄호를 사용할 수 없다.

위 두가지 특징을 염두해두고 문제 케이스에 대해 살펴 보기로 했다.

예제 입력 1에 있는 예시를 가지고 먼저 가능한 케이스에 대해 고려 해보면

• (3+8)*7-9*2
• (3+8)*(7-9)*2
• (3+8)*7-(9*2)
• 3+(8*7)-9*2
• 3+(8*7)-(9*2)
• 등등...

위 케이스들을 고려하면서 괄호를 추가하는 것에 대한 규칙성이 있는지에 대해 고민을 해보았지만 규칙이 보이지 않았다. 문제에서 주어진 N의 최대 길이가 19이고 시간 제한이 0.5초이기 때문에 따로 규칙을 고려하지 않고, 가능한 모든 경우의 수를 다 찾더라도 시간내에 풀 수 있을 것이라고 생각했다. 

먼저 주어진 입력을 받기 위한 버퍼를 정의했다. 이 후 연산자와 숫자를 따로 처리하는 것이 편할 것 같아서 각각을 받는 ArrayList 를 정의했다. 입력값에는 (zerobased index 기준) 0을 포함한 짝수번째 값에는 숫자, 홀수번째 값에는 연산자가 들어오는 규칙이 있기 때문에 이를 활용해서 입력값을 저장해 주었다. 

이제 정답값을 구하기 위한 솔루션만 구현하면 되고 이는 완전탐색을 위해 dfs를 활용하여 구현하기로 했다. 이 때 괄호를 사용하지 않는 경우의 값 또한 구해주어야 한다는 점을 고려해야 한다. 연산자 인덱스를 기준으로 계산을 생각해서 구현했다. 

사실 처음에는 괄호를 어떻게 처리해야 할 지 감이 잘 오지 않았다. 그 이유는 수식 앞에서 부터 순서대로 괄호를 넣는 케이스를 예시로 생각했었고 아래와 같이 앞에서 부터 케이스별로 괄호를 넣을 수 있는 방법을 구현하려고 하니 복잡하고 잘 떠오르지 않아서 많이 헤맸다. 

e.g.) 
1. 3+8*7-9*2 (= (3+8)*7-9*2))
2. 3+(8*7)-9*2
3. 3+(8*7)-(9*2)

...

하루정도 리프레쉬를 하고.. 다시 생각해보니 백트래킹으로 풀면 되는데.. 라는 생각이 들어서 아래와 같이 구현했다. 연산자 인덱스를 기준으로 조건문을 생각했고, 모든 경우의 수를 다 계산할 수 있는 방법이다. 

연산에 대한 함수는 따로 분리해주었다. 위 switch-case 문은 자바 11 에서는 지원하지 않는 문법(자바 11이후 부터 지원하는 문법)이라 백준에 제출할 때는 기존 switch-case expression을 사용해서 제출했다. 물론 if문을 사용해도 무방하다. 

아직까지 백트래킹에 대한 아이디어가 바로바로 떠오르지 않는 것을 보니 더 연습이 필요하다고 느꼈다.