Java 백준 문제풀이 (36) 연산자 끼워넣기

 

삼성 SW 역량 테스트 기출 문제라고 한다.

맨날 무슨 초등부 중등부 올림피아드 문제들만 있어서 안 풀리면 자괴감 들었었는데, 삼성 코테 기출문제라고 하니 의욕이 더 솟아 올랐다.

 

문제 자체는 백트래킹만 할 줄 알면 누구나 풀 수 있을 정도로 쉽다.

백트래킹을 할 줄 모르면 당연히 DFS 알고리즘과 백트래킹은 배워와야 한다..

 

1. 주어지는 정수와 기호를 배열로 받는다.

2. 기호의 개수가 정해져 있으니 중복순열이 아닌 순열을 구하는 방식으로 백트래킹해야 한다.

3. 백트래킹 + 브루트 포스를 활용하여 모든 경우의 수를 구한 뒤 최소값과 최대값을 출력하면 끝.

 

다만 늘 그렇듯 더 효율적인 풀이 방법이 있고 비효율적인 풀이 방법이 있다.

나는 풀고나서 다른 사람들의 정답을 보니 쓸데없이 한 바퀴 더 돌아서 문제를 풀었다는 걸 알게 되었는데, 이건 코딩 실력 자체의 문제라서 좀 더 효율적인 코드를 작성하기 위해 꾸준 히 노력해야 할 것 같다..

 

일단 두가지 답안을 모두 공유한다.

 

 

 

 

 

 

1. 비효율 답안 ( ㅜㅜ )

 

 

import java.io.*;
import java.util.ArrayList;
import java.util.StringTokenizer;
 
public class Main {
    final static int SIGN = 4; // 사인 종류
    static int[] numArr; // 주어지는 숫자
    static ArrayList<String> signList = new ArrayList<>(); // 사칙연산 기호 리스트
    static int min = Integer.MAX_VALUE; // 최소값 대입할 변수
    static int max = Integer.MIN_VALUE; // 최대값 대입할 변수
 
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st;
 
        int T = Integer.parseInt(br.readLine()); // 수의 개수
        st = new StringTokenizer(br.readLine(), " ");
        numArr = new int[T];
 
        for (int i = 0; i < T; i++) {
            numArr[i] = Integer.parseInt(st.nextToken());
        }
 
        st = new StringTokenizer(br.readLine(), " ");
        // 정수로 받은 인풋값을 기호로 변환하여 리스트에 삽입한다
        addSignList(st, signList);
 
        ArrayList<String> temp = new ArrayList<>();
        boolean[] visited = new boolean[signList.size()]; // 방문 여부 체크
 
        backtracking(0, temp, visited);
 
        System.out.println(max);
        System.out.println(min);
    }
    
    // 백트래킹 메서드
    private static void backtracking(int v, ArrayList<String> temp, boolean[] visited) {
        if (signList.size() == temp.size()) {
            int result = numArr[0];
            // 기호의 개수는 늘 N-1이다
            for (int i=0; i<temp.size(); i++) {
                result = calculate(result, temp.get(i), numArr[i+1]);
            }
 
            if (result > max) {
                max = result;
            }
 
            if ( result < min ) {
                min = result;
            }
 
            return;
        }
 
        for (int i=0; i< signList.size(); i++) {
            if (!visited[i]) {
                visited[i] = true;
                temp.add(signList.get(i));
                backtracking(i, temp, visited);
                visited[i] = false;
                temp.remove(temp.size() - 1);
            }
        }
    }
    
    private static void addSignList(StringTokenizer st, ArrayList<String> signList) {
        for (int i = 0; i < SIGN; i++) {
            int token = Integer.parseInt(st.nextToken());
 
            for (int j = 0; j < token; j++) {
                switch (i) {
                    case 0:
                        signList.add("+");
                        break;
                    case 1:
                        signList.add("-");
                        break;
                    case 2:
                        signList.add("*");
                        break;
                    case 3:
                        signList.add("/");
                        break;
                    default:
                        throw new RuntimeException();
                }
            }
        }
    }
 
    private static int calculate(int num1, String sign, int num2) {
        switch (sign) {
            case "+" :
                return num1+num2;
            case "-" :
                return num1-num2;
            case "*" :
                return num1*num2;
            case "/" :
                return num1/num2;
            default:
                throw new RuntimeException();
        }
    }
}

 

 

 

 

 

2. 효율적인 답안

 

 

import java.io.*;
import java.util.StringTokenizer;
 
public class Main {
    final static int SIGN = 4; // 사인 종류
    static int[] numArr; // 초기 입력값
    static int[] signArr = new int[SIGN]; // 사인 배열
    static int min = Integer.MAX_VALUE; // 최소값 대입할 변수
    static int max = Integer.MIN_VALUE; // 최대값 대입할 변수
 
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st;
 
        int T = Integer.parseInt(br.readLine()); // 수의 개수
        st = new StringTokenizer(br.readLine(), " ");
        numArr = new int[T];
 
        // 정수 입력
        for (int i = 0; i < T; i++) {
            numArr[i] = Integer.parseInt(st.nextToken());
        }
 
        // 연산자 입력
        st = new StringTokenizer(br.readLine(), " ");
        for (int i = 0; i < SIGN; i++) {
            signArr[i] = Integer.parseInt(st.nextToken());
        }
 
        backtracking(numArr[0], 1);
 
        System.out.println(max);
        System.out.println(min);
    }
 
    // 백트래킹 메서드
    private static void backtracking(int num, int index) {
        if (index == numArr.length) {
            max = Math.max(max, num);
            min = Math.min(min, num);
            return;
        }
 
        for (int i=0; i<signArr.length; i++) {
            if (signArr[i] > 0) {
                signArr[i]--;
                switch (i) {
                    case 0 :
                        backtracking(num+numArr[index], index+1);
                        break;
                    case 1 :
                        backtracking(num-numArr[index], index+1);
                        break;
                    case 2 :
                        backtracking(num*numArr[index], index+1);
                        break;
                    case 3 :
                        backtracking(num/numArr[index], index+1);
                        break;
                }
 
                signArr[i]++;
            }
        }
    }
}
 

 

 

 

 

 

내가 푼 방법에 비해 메모리도 25% 절약했고 , 시간은.. 할말하않 ㅎ

늘 어려운 재귀.. 분할해서 생각하는 것까지는 하겠는데 내가 처음부터 저렇게 합쳐서 코드 작성하는 건 너무 어려운 일인 것 같다

풀고 또 풀다보면 늘겠지..