[Baekjoon(JAVA) - Algorithm] 14888번: 연산자 끼워넣기

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

 

---

문제를 풀기 위해 Backtracking 알고리즘을 알아야 한다.

Backtracking이란 재귀적으로 문제를 하나씩 풀어가면서 현재 재귀를 통해 확인 중인 노드가 조건에 위배되는지 판단하고, 해당 노드가 조건을 위배한다면 그 노드를 제외하고 다음 단계로 나아가는 방식이다.

즉, 현재 상태에서 다음 상태로 가는 모든 경우의 수를 찾아서 모든 경우의 수가 더 이상 맞지 않다고 판단되면 이전의 상태로 돌아가는 것이다.

따라서 DFS를 통해 모든 경우의 수를 깊이 우선 탐색을 하면서 더 이상 필요 없는 부분을 가지치기하는 행위를 Backtracking이다.

 

이제 DFS를 알아보자.

https://cobi-98.tistory.com/30#google_vignette

DFS(깊이 우선 탐색, Depth-First Search)는 하나의 순환 알고리즘으로 Backtracking에 사용하는 대표적인 탐색 알고리즘이다.

루트 노드(혹은 다른 임의의 노드)에서 시작해서 다음 분기로 넘어가기 전에 해당 분기를 완벽하게 탐색하는 방식을 말한다.

주로, 재귀함수 또는 Stack으로 구현한다.

 

- DFS의 시간복잡도 (V: 노드 수, E: 간선 수)

• 인접 행렬에서의 시간복잡도 : O(V^2)
• 인접 리스트에서의 시간복잡도 : O(V+E)

- DFS의 장단점

• 장점
  • 현재 경로상의 노드들만 기억하면 되므로 저장 공간이 비교적 적게 든다.
  • DFS가 BFS보다 좀 더 간단하다. (ex. 그래프의 모든 노드를 방문하는 문제)
  • 목표 노드가 깊은 단계에 있을 경우 답을 빨리 구할 수 있다.
• 단점
  • 답이 없는 경로에 깊이 빠질 가능성이 있다.
    따라서 임의의 깊이까지만 탐색하고, 목표 노드를 발견하지 못하면 다음 경로를 따라 탐색하는 방법이 유용하다.
  • 얻은 답이 최단 경로가 된다는 보장이 없다.
    이유는 목표에 이르는 경로가 다수인 문제에 대해 DFS는 답에 다다르면 탐색을 끝내기 때문이다.

 

이제 이 문제를 풀기 위해 Backtracking에 사용하는 DFS 알고리즘을 재귀함수를 통해 구현해 보자.

Answer

import java.io.InputStreamReader;
import java.io.BufferedReader;
import java.io.IOException;
import java.util.StringTokenizer;

public class Main {
    static final int OPERATOR_COUNT = 4;
    static int max = Integer.MIN_VALUE;
    static int min = Integer.MAX_VALUE;

    static int[] numbers;
    static int[] operators = new int[OPERATOR_COUNT];

    public static void main(String[] args) {
        try (BufferedReader br = new BufferedReader(new InputStreamReader(System.in))) {
            int numberCount = Integer.parseInt(br.readLine());
            StringTokenizer numTokens = new StringTokenizer(br.readLine(), " ");
            StringTokenizer operatorTokens = new StringTokenizer(br.readLine(), " ");

            numbers = new int[numberCount];
            for (int i = 0; i < numbers.length; i++) {
                numbers[i] = Integer.parseInt(numTokens.nextToken());
            }

            for (int i = 0; i < operators.length; i++) {
                operators[i] = Integer.parseInt(operatorTokens.nextToken());
            }
        } catch (IOException e) {
            System.err.println("ERROR" + e.getMessage());
        }

        int baseNum = numbers[0];
        dfs(baseNum, 1);

        StringBuilder sb = new StringBuilder();
        sb.append(max).append("\n");
        sb.append(min);
        System.out.print(sb);
    }

    static void dfs(int num, int idx) {
        if (idx == numbers.length) {
            max = Math.max(max, num);
            min = Math.min(min, num);
            return;
        }

        for (int i = 0; i < operators.length; i++) {
            if (operators[i] > 0) {
                operators[i]--;

                switch (i) {
                    case 0:
                        dfs(num + numbers[idx], idx + 1);
                        break;
                    case 1:
                        dfs(num - numbers[idx], idx + 1);
                        break;
                    case 2:
                        dfs(num * numbers[idx], idx + 1);
                        break;
                    case 3:
                        dfs(num / numbers[idx], idx + 1);
                        break;
                }
                operators[i]++;
            }
        }
    }
}

 

Code Review

static final int OPERATOR_COUNT = 4;
static int max = Integer.MIN_VALUE;
static int min = Integer.MAX_VALUE;

static int[] numbers;
static int[] operators = new int[OPERATOR_COUNT];

뒤에서 `dfs()` 메서드에 사용하기 위해 전역 변수를 선언한다.

주어진 연산자가 +, -, *, / 4가지로 주어졌으므로 `OPERATOR_COUNT`를 final로 선언한다.

최대, 최솟값을 0으로 초기화하는 것보다 안정성이 있다고 생각하여 Integer.MIN_VALUE, MAX_VALUE로 초기화했다.

 

입력받은 수열을 저장할 `numbers` 배열과 연산자 개수를 저장할 `operators` 배열을 선언한다. 이때 연산자 크기는 정해져 있으므로 그 크기로 초기화를 한다. (`numbers` 배열은 첫 행을 입력받았을 때 그 크기로 초기화한다.)

 

try (BufferedReader br = new BufferedReader(new InputStreamReader(System.in))) {
    int numberCount = Integer.parseInt(br.readLine());
    StringTokenizer numTokens = new StringTokenizer(br.readLine(), " ");
    StringTokenizer operatorTokens = new StringTokenizer(br.readLine(), " ");

    numbers = new int[numberCount];
    for (int i = 0; i < numbers.length; i++) {
        numbers[i] = Integer.parseInt(numTokens.nextToken());
    }

    for (int i = 0; i < operators.length; i++) {
        operators[i] = Integer.parseInt(operatorTokens.nextToken());
    }
} catch (IOException e) {
    System.err.println("ERROR" + e.getMessage());
}

`try-with-resources`로 try에 객체의 자원을 받아서 try문이 종료되면 자동으로 자원을 반환한다.

`System.in`으로 사용자로부터 입력받은 데이터를 바이트 스트림으로 받는다.

`InputStreamReader` 클래스로 바이트 스트림을 문자 기반 스트림으로 받는다.

`BufferedReader` 클래스로 문자 스트림을 읽는다.

 

첫째 줄에 수의 개수가 주어지므로 `br.readLine()`으로 문자열을 읽어 들여서 `Integer.parseInt()`로 정수 변환 후 변수에 대입한다. (이 변수는 `numbers` 배열의 크기가 된다.)

둘째 줄과 셋째 줄은 공백으로 입력이 나누어져 있으므로 각 행에 대해 `StringTokenizer` 객체 `numTokens`, `operatorTokens`를 생성한다.

 

`numbers`, `operators` 배열 모두 for문을 통해 `nextToken()` 메서드를 사용하여 배열에 순서대로 넣어준다.

 

int baseNum = numbers[0];
dfs(baseNum, 1);

기준이 될 첫 번째 수를 `number[0]`에서 가져온다.

`dfs()` 메서드를 첫번째 수인 `baseNum`과 그다음 순서인 인덱스 1을 인자로 호출한다.

 

이제 dfs 알고리즘을 재귀함수로 만들어보자.

static void dfs(int num, int idx) {
    if (idx == numbers.length) {
        max = Math.max(max, num);
        min = Math.min(min, num);
        return;
    }

    for (int i = 0; i < operators.length; i++) {
        if (operators[i] > 0) {
            operators[i]--;

            switch (i) {
                case 0:
                    dfs(num + numbers[idx], idx + 1);
                    break;
                case 1:
                    dfs(num - numbers[idx], idx + 1);
                    break;
                case 2:
                    dfs(num * numbers[idx], idx + 1);
                    break;
                case 3:
                    dfs(num / numbers[idx], idx + 1);
                    break;
            }
            operators[i]++;
        }
    }
}

`dfs()` 메서드는 파라미터로 기준이 될 숫자 `num`과 다음 수의 인덱스 `idx`를 지닌다.

따라서 `idx`가 `numbers` 배열의 크기와 같으면 더 이상의 숫자는 없으므로 Math 클래스의 max(), min() 메서드로 최대, 최솟값을 구한다. (조건과 다르면 아래 for문 동작)

 

for문으로 `operators` 연산자 배열을 반복할 것인데 개수가 1개 이상인 경우만 반복해야 하니 `operators[i] > 0` 조건을 건다.

해당 연산자의 개수가 1개 이상일 때 `operators[i]--`로 개수를 1 줄여주고, `switch-case`문으로 연산자의 위치를 확인한다.

 

i가 0이면 '+', 1이면 '-', 2이면 '*', 3이면 '/' 연산을 하도록 한다.

위에서 얻어온 연산자로 기준이 되는 수 `num`과 `number` 배열의 `idx`번째 수를 연산한다.

이 연산이 다음 `dfs()` 메서드의 첫 번째 인자가 되고, 두 번째 인자는 `idx + 1`하여 다음 `numbers` 배열의 인덱스가 된다.

 

`numbers` 배열의 다음 인덱스로 그 수를 연산하는 작업을 `dfs()` 메서드를 다시 호출하면서 재귀를 돌리고 끝이 나면 그때의 연산자의 개수를 `operators[i]++`로 1 증가시킴으로써 연산자 순서를 바꿔가며 탐색해 간다.

 

이 문제의 세 번째 입력을 예시로 들어보자.

6
1 2 3 4 5 6
2 1 1 1

 

계산식	연산자 배열, idx	계산 결과	max	min
1	[2, 1, 1, 1], 1	1
1 + 2	[1, 1, 1, 1], 1 -> 2	3
1 + 2 + 3	[0, 1, 1, 1], 2 -> 3	3 + 3 = 6
1 + 2 + 3 - 4	[0, 0, 1, 1], 3 -> 4	6 - 4 = 2
1 + 2 + 3 - 4 * 5	[0, 0, 0, 1], 4 -> 5	2 * 5 = 10
1 + 2 + 3 - 4 * 5 / 6	[0, 0, 0, 0], 5 -> 6	10 / 6 = 1
	[0, 0, 0, 0], 6		1 vs 1 -> 1	1 vs 1 -> 1
Backtracking1
1 + 2 + 3 - 4 * 5	[0, 0, 0, 1], 6 -> 5	10
1 + 2 + 3 - 4	[0, 0, 1, 1], 5 -> 4	2
1 + 2 + 3 - 4 / 5	[0, 0, 1, 0], 4 -> 5	2 / 5 = 0
1 + 2 + 3 - 4 / 5 * 6	[0, 0, 0, 0], 5 -> 6	0 * 6 = 0
	[0, 0, 0, 0], 6		1 vs 0 -> 1	1 vs 0 -> 0
Backtracking2
1 + 2 + 3 - 4 * 5	[0, 0, 1, 0], 6 -> 5	0
1 + 2 + 3 - 4	[0, 0, 1, 1], 5 -> 4	2
1 + 2 + 3	[0, 1, 1, 1], 4 -> 3	6
1 + 2 + 3 * 4	[0, 1, 0, 1], 3 -> 4	6 * 4 = 24
1 + 2 + 3 * 4 - 5	[0, 0, 0, 1], 4 -> 5	24 - 5 = 19
1 + 2 + 3 * 4 - 5 / 6	[0, 0, 0, 0], 5 -> 6	19 / 6 = 3
	[0, 0, 0, 0], 6		1 vs 3 -> 3	0 vs 3 -> 0
Backtracking3
...

위 표처럼 모든 경우의 수를 탐색한 후 Backtracking 부분에서 다시 되돌아가며 다시 탐색하는 식으로 재귀함수를 사용한다.

 

Result

이번 문제도 학습이 필요한 부분이었다. (시간이 조금 지난 후에 다시 풀어보자..)

 

References

https://cobi-98.tistory.com/30#google_vignette

 

https://chanhuiseok.github.io/posts/algo-23/