sw expert academy 4008번 숫자 만들기 자바(java) 풀이
문제정리
- 연산자와 숫자가 주어질때 가능한 수식을 계산하여 최대와 최소값을 구해라.
- 연산자의 우선순위는 고려하지 않고 왼쪽에서 오른쪽으로 차례대로 계산한다.
- 연산자의 개수는 숫자의 개수보다 항상 1개 작다.
- 숫자의 순서는 바꿀 수 없다.
- 나눗셈에서 소수점 이하는 버린다.
- 수식을 완성할때 주어진 카드를 모두 사용해야 한다.
문제풀이
숫자는 순서가 바뀌지 않으므로 연산자의 순서만 조정해주면 됩니다.
그러기 위해서 백트래킹을 통해서 모든 가능한 순서를 찾아주어야 합니다.
그리고 계산을 하면 됩니다. 계산할 때 첫번째 연산자는 2번째 숫자와 3번째 연산자는 그전에 계산된 값에 4번째 숫자와 계산하게 됩니다.
그리고 최대 최소를 구하기 위해서 Collections.min과 max 함수를 이용합니다.
중복된 값이 있을 경우 제거 하기 위해서 Set을 이용하였지만 arraylist를 이용해도 됩니다.
BOJ의 연산자 끼워넣기
BOJ의 연산자 끼워넣기 문제와 거의 같습니다.
그래서 permutation을 이용하여 모든 경우를 구해서 하였더니
이 문제에서는 마지막 tc에서 메모리 초과나 시간초과가 나왔습니다.
12개의 순열을 구하는 과정에서 시간이 많이 소모되는 것 같습니다.
그리고 재귀를 돌다보니 deep하게 들어가서 메모리가 부족한 것 같습니다...
```
dfs
- op배열에 가능한 연산자 숫자 개수가 담겨 있습니다.
- 4개의 연산자를 백트래킹을 통해 모두 사용합니다.
- 사용한 경우 op배열에서 1을 빼줍니다.
- dfs를 재귀를 통해 depth가 N-1까지 반복합니다.
- dfs를 나오면 사용했던 것을 풀어주기 위해 op배열에서 1을 다시 더해줍니다.
- depth가 N-1까지 반복했다면 stack에 담긴 선택한 연산자를 가지고 계산합니다.
swea 숫자 만들기 자바 코드