백준 14888 연산자 끼워넣기 Java

단계별로 풀어보기 -> 백트래킹에 있는 있는 문제이며

삼성 SW 역량테스트 기출문제 이기도 한 연산자 끼워넣기 문제이다.

 

한 번에 맞히긴 했지만 다른 분들의 소스와 시간 차이가 너무 많이 나서

내가 한 방법과 그들의 방법을 비교하며 정리하고자 한다.

 

문제의 내용은

N개의 수가 주어지고

더하기, 빼기, 곱하기, 나누기 순으로 몇 개를 사용할 수 있는지가 주어진다.

N개의 수의 순서는 변하지 않는다.

연산자를 끼워넣어서 만들 수 있는 최댓값과 최솟값을 출력하면 되는 문제이다.

 

내가 한 방법은 만들 수 있는 연산자의 모든 경우를 백트래킹으로 탐색해서

연산자의 길이가 N-1이면 직접 계산해서 최댓값과 최솟값을 구했다.

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.List;
import java.util.StringTokenizer;
 
public class Q14888 {
    public static int n;
    public static int [] a = new int[12];
    public static List<Character> list = new ArrayList<>();
    public static char [] type = {'+', '-', '*', '/'};
    public static boolean [] visited;
    public static int min = Integer.MAX_VALUE;
    public static int max = Integer.MIN_VALUE;
    
    public static void backtrack(String s) {
        if(s.length() == n-1) {
            int result = calculation(s);
            min = Math.min(min, result);
            max = Math.max(max, result);
        }
        for(int i=0; i<list.size(); i++) {
            if(!visited[i]) {
                visited[i] = true;
                backtrack(s+list.get(i));
                visited[i] = false;
            }
        }
    }
    
    public static int calculation(String s) {
        int index = 1;
        int result = a[0];
        for(int i=0; i<s.length(); i++) {
            if(s.charAt(i)=='+') {
                result+=a[index++];
            } else if(s.charAt(i)=='-') {
                result-=a[index++];
            } else if(s.charAt(i)=='*') {
                result*=a[index++];
            } else if(s.charAt(i)=='/') {
                result/=a[index++];
            }
        }
        return result;
    }
    public static void main(String[] args) throws IOException{
        BufferedReader reader = new BufferedReader(new InputStreamReader(System.in));
        n = Integer.parseInt(reader.readLine());
        StringTokenizer st = new StringTokenizer(reader.readLine());
        for(int i=0; i<n; i++) {
            a[i] = Integer.parseInt(st.nextToken());
        }
        st = new StringTokenizer(reader.readLine());
        for(int i=0; i<4; i++) {
            int k = Integer.parseInt(st.nextToken());
            for(int j=0; j<k; j++) {
                list.add(type[i]);
            }
        }
        visited = new boolean[list.size()];
        backtrack("");
        System.out.println(max);
        System.out.println(min);
    }
}

다른 분들이 한 방법은 연산자 별로 받은 개수로 결괏값을 계산하며 백트래킹을 해 나가는 방식이다.

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;
 
public class Q1488_ver2 {
    public static int n;
    public static int [] a = new int[12];
    public static int [] operator = new int[4];
    public static int min = Integer.MAX_VALUE;
    public static int max = Integer.MIN_VALUE;
    
    public static void dfs(int index, int result) {
        if(index == n) {
            min = Math.min(min, result);
            max = Math.max(max, result);
            return;
        }
        if(operator[0] > 0) {
            operator[0]--;
            dfs(index+1, result+a[index]);
            operator[0]++;
        }
        if(operator[1] > 0) {
            operator[1]--;
            dfs(index+1, result-a[index]);
            operator[1]++;
        }
        if(operator[2] > 0) {
            operator[2]--;
            dfs(index+1, result*a[index]);
            operator[2]++;
        }
        if(operator[3] > 0) {
            operator[3]--;
            dfs(index+1, result/a[index]);
            operator[3]++;
        }
    }
 
    public static void main(String[] args) throws IOException{
        BufferedReader reader = new BufferedReader(new InputStreamReader(System.in));
        n = Integer.parseInt(reader.readLine());
        StringTokenizer st = new StringTokenizer(reader.readLine());
        for(int i=0; i<n; i++) {
            a[i] = Integer.parseInt(st.nextToken());
        }
        st = new StringTokenizer(reader.readLine());
        for(int i=0; i<4; i++) {
            operator[i] = Integer.parseInt(st.nextToken());
        }
        dfs(1, a[0]);
        StringBuilder sb = new StringBuilder();
        sb.append(max+"\n");
        sb.append(min);
        System.out.println(sb.toString());
    }
}

다른 분들이 푼 방식이 코드도 훨씬 깔끔하고 실행 속도도 월등히 빠르다.

적당히 차이나면 괜찮은데 속도면에서 약 18배 정도 차이가 난다....ㅎ 

 

어떻게 이렇게 차이가 많이 났을까 살펴보니

우선 계산을 하는 과정에서 차이가 많이 났다.

나의 경우엔 일단 연산자의 조합을 가능한 모든 경우를 구하고 계산하는 메서드를 또 써서 계산했는데

다른 분들은 계산을 하면서 백트래킹을 해나갔다.

계산하는 메소드가 O(N)의 시간 복잡도를 가지기 때문에 

시간 차이가 났을 것이다. 

그리고

백트래킹 메소드의 호출 횟수도 약 2배 차이 났다.

정확한 이유는 모르겠지만 아마도

나의 경우엔 백트래킹에서 for문이 0부터 다시 돌아가서 쓸데없이 호출하는 횟수가 많았다면

다른 분들의 코드 같은 경우엔 앞으로 쭉쭉 나아가면서 백트래킹 하기 때문에

호출 횟수에서 차이가 나지 않았을까 생각한다. 

 

결론적으로 아직 너무 못한다..  열심히 공부해서 효율적으로 잘 짜는 사람이 돼야겠다!