[백준, 14888번] 연산자 끼워넣기 (브루트 포스, 백트래킹, Java)

문제설명

입력 & 출력

나의 풀이

문제 접근 방법

"백준 - 연산자 끼워넣기" 문제는 N개의 수열이 주어지고, N-1개의 연산자가 +, -, * ,/ 순서대로 주어질 때 각 수와 연산자를 조합해서 최댓값과 최솟값을 구하는 문제입니다.

 

이 때 식의 계산은 기존의 연산자 우선 순위를 무시하고 앞에서부터 진행해야 합니다.

 

수열의 끝까지 연산자를 조합해서 계산해야 하며, 각 연산자의 개수가 제한되어 있어 특정 연산자를 더 이상 사용할 수 없는 경우가 발생합니다.

수열: [1, 2, 3, 4, 5]
연산자: [+(1개), -(2개), *(1개), /(0개)]

 

위와 같이 입력이 주어질 때  '+' 연산자는 1번 사용을 하면 더 이상 사용하지 못합니다.

 

이러한 특성 때문에 가능한 모든 경우를 탐색하되, 특정 연산자를 더 이상 사용할 수 없는 경우는 탐색을 중단하는 백트래킹 방식을 사용하면 효율적으로 문제를 해결할 수 있습니다.

---

 

예제 입력2를 수열과 연산자로 표현하면 위와 같습니다. 이 수열과 연산자를 DFS 알고리즘과 백트래킹을 통해 접근하는 과정을 살펴보겠습니다.

---

 

이 문제의 핵심은 DFS와 백트래킹을 활용하여 가능한 모든 연산자 조합을 탐색하는 것입니다. 위 그림과 같이, 매 단계에서 사용 가능한 연산자를 선택하여 연산을 수행하고, 해당 연산자의 개수를 감소시킵니다.

 

이때 하늘색 노드는 현재 사용 가능한 연산자를, 분홍색 노드는 이미 사용한연산자를 나타냅니다.

 

DFS를 통해 더 깊은 단계로 진행하면서 남은 연산자들로 계산을 이어가고, 최종적으로 수열의 끝까지 도달하면 그 결과값을 저장합니다. 이러한 과정을 통해 가능한 모든 조합의 결과값들 중 최댓값(35) 과 최솟값(17)을 찾아낼 수 있습니다.

---

전체 코드

 

코드는 크게 2가지로 구분되어 있습니다.

 

1. main 문

 

main 문에서는 입력을 BufferedReader 클래스와 StringTokeinzer클래스를 사용하여 빠른 입력처리와 토큰을 사용하여 분리를 해주었습니다.

 

2. dfs 함수

 

dfs함수에서는 중요한 부분은 크게 2가지로 나뉩니다. DFS 알고리즘에서 중요한 탈출 조건과 재귀 호출입니다.

• num[] : 순열을 저장한 배열
• op[] : 연산자의 개수를 순서대로 저장한 배열
• count
  • 사용한 연산자의 개수
  • 다음에 사용할 숫자의 인덱스를 결정 (count + 1)
• currValue : 현재까지의 계산 결과

DFS 함수는 크게 두 부분으로 구성됩니다. 먼저 탈출 조건을 확인하고, 그 다음 가능한 연산자들을 탐색합니다.

 

탈출 조건은 단순합니다. 문제에서 N개의 숫자와 N-1개의 연산자가 주어지므로, 사용한 연산자의 개수(count)가 N-1과 같아지면 모든 연산자를 사용했다는 의미입니다. 이 시점에서 현재까지의 계산 결과와 이전에 저장된 최댓값, 최솟값을 비교하여 갱신합니다.

 

연산자 탐색 과정에서는 네 가지 연산자(+, -, *, /)에 대해 반복문을 수행합니다.

 

각 연산자의 남은 개수가 0보다 크다면, 해당 연산자를 사용할 수 있다는 의미입니다. 연산자를 선택하면 그 개수를 1 감소시키고, 선택한 연산자로 계산을 수행한 결과값과 함께 다음 단계(count + 1)로 재귀 호출을 진행합니다.

 

이러한 과정을 통해 가능한 모든 연산자 조합을 탐색하면서, 최적의 결과값을 찾아낼 수 있습니다.