[백준 *Java] - 4연산(14395)

4연산

14395번: 4연산

문제

정수 s가 주어진다. 정수 s의 값을 t로 바꾸는 최소 연산 횟수를 구하는 프로그램을 작성하시오.

사용할 수 있는 연산은 아래와 같다.

1. s = s + s; (출력: +)
2. s = s - s; (출력: -)
3. s = s * s; (출력: *)
4. s = s / s; (출력: /) (s가 0이 아닐때만 사용 가능)

입력

첫째 줄에 s와 t가 주어진다. (1 ≤ s, t ≤ 109)

출력

첫째 줄에 정수 s를 t로 바꾸는 방법을 출력한다. s와 t가 같은 경우에는 0을, 바꿀 수 없는 경우에는 -1을 출력한다. 가능한 방법이 여러 가지라면, 사전 순으로 앞서는 것을 출력한다. 

연산의 아스키 코드 순서는 '*', '+', '-', '/' 이다.

---

👇 접근 방식

문제를 읽어보니, bfs로 풀어야 한다는 생각을 했고, 문제에서 언급한 조건들만 잘 처리해주면 될 거 같다는 생각을 했습니다.

첫 번째 설계입니다.
먼저 신경써야할 부분은
1. bfs 탈출조건이 무엇인지,
: 저는 탈출 조건을 k의 수를 넘어갈 때 Queue에 offer를 할 수 없게끔 하였으며, 나눗셈은 처음에만 사용하게끔하고 그 이후에 나눗셈을 해볼 필요가 없다고 생각하여, 처음 나눗셈 작업을 했다면 flag = true를 설정하여 연산작업 4가지 중 3가지만 하게끔 설정합니다.
2. s가 나눗셈을 해야할 경우, 0이 아닐 때만 사용이 가능하다.
애초에 연산처리를 한 뒤에, 0이 될 경우 Queue에 offer를 하지 않습니다.
3. 가능한 방법이 여러 가지라면? 사전 순으로 앞서는 것을 출력한다 연산 아스키코드 순서는 (*, +, -, /)
연산 작업 순서를 아스키코드 순서로 하게끔 배열을 지정합니다.
4. 방문처리를 이용하여, 중복되는 상황을 줄이기
boolean을 미리 10억만큼 공간을 할당하여서 , 연산해서 나온 숫자를 방문처리를 해줍니다.
5. 변수 타입 신경쓰기 int -> long

 

 

아래는 성공한 코드입니다.

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

public class Main {
    static boolean[] visited = new boolean[1_000_000_001]; // 10의 9승
    static final char[] operators = {'*', '+', '-', '/'};
    static boolean flag;
    static class Node {
        int s;
        String operator;

        public Node(int s, String operator) {
            this.s = s;
            this.operator = operator;
        }
    }
    static String bfs (int s, int t) {
        String result = "-1";
        if (s == t) return "0";

        Queue<Node> qu = new LinkedList<>();
        visited[s] = true;
        qu.offer(new Node(s, ""));

        while (!qu.isEmpty()) {
            Node curNode = qu.poll();

            if (curNode.s == t) return curNode.operator;
            for (int i = 0; i < operators.length; i++) {
                if (flag && operators[i] == '/') continue;
                long operateS = operateNumber(i, curNode.s);
                if (operateS > t) continue;

                int castingS = (int)operateS;
                if (curNode.s == 0) continue;
                if (visited[castingS]) continue;

                visited[castingS] = true;
                qu.offer(new Node(castingS, operatorAdd(curNode.operator, operators[i])));
            }
        }

        return result;
    }

    static String operatorAdd(String operator, char addOperator) {
        StringBuilder sb = new StringBuilder();
        sb.append(operator).append(addOperator);
        return sb.toString();
    }

    static long operateNumber(int i, int s) {
        long castingS = s;
        switch (operators[i]) {
            case '+' :
                castingS = castingS + castingS;
                break;
            case '-' :
                castingS = castingS - castingS;
                break;
            case '*' :
                castingS = castingS * castingS;
                break;
            case '/' :
                castingS = castingS / castingS;
                flag = true;
                break;
        }
        return castingS;
    }

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());

        int s = Integer.parseInt(st.nextToken());
        int t = Integer.parseInt(st.nextToken());
        System.out.println(bfs(s, t));
    }
}

 

위의 코드 복잡도는 아래와 같습니다. 

 

리팩토링

리팩토링은 방문처리를 boolean 으로하는 게 아닌, Set이라는 자료구조를 이용합니다.

그리고, int를 long으로 캐스팅 작업을 하는 게 아닌, long으로 타입을 지정하여 사용합니다.

아래는 리팩토링 한 코드입니다.

 

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

public class Main {
    static Set<Long> list = new HashSet<>();
    static final char[] operators = {'*', '+', '-', '/'};
    static boolean flag;
    static class Node {
        long s;
        String operator;

        public Node(long s, String operator) {
            this.s = s;
            this.operator = operator;
        }
    }
    static String bfs (long s, int t) {
        String result = "-1";
        if (s == t) return "0";

        Queue<Node> qu = new LinkedList<>();
        list.add(s);
        qu.offer(new Node(s, ""));

        while (!qu.isEmpty()) {
            Node curNode = qu.poll();

            if (curNode.s == t) return curNode.operator;
            for (int i = 0; i < operators.length; i++) {
                if (flag && operators[i] == '/') continue;
                long operateS = operateNumber(i, curNode.s);
                if (operateS > t) continue;
                if (curNode.s == 0) continue;

                if (!list.contains(operateS)) {
                    list.add(operateS);
                    qu.offer(new Node(operateS, operatorAdd(curNode.operator, operators[i])));
                }

            }
        }

        return result;
    }

    static String operatorAdd(String operator, char addOperator) {
        StringBuilder sb = new StringBuilder();
        sb.append(operator).append(addOperator);
        return sb.toString();
    }

    static long operateNumber(int i, long s) {
        switch (operators[i]) {
            case '+' :
                s = s + s;
                break;
            case '-' :
                s = s - s;
                break;
            case '*' :
                s = s * s;
                break;
            case '/' :
                s = s / s;
                flag = true;
                break;
        }
        return s;
    }

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());

        int s = Integer.parseInt(st.nextToken());
        int t = Integer.parseInt(st.nextToken());
        System.out.println(bfs(s, t));
    }
}

 

위 코드의 메모리, 시간 복잡도는 아래와 같습니다.