[백준] 14395번 4연산(JAVA)

문제

- 주어진 정수 s의 값을 t로 바꾸는 최소 연산 순서 구하기

- s = s + s; (출력 : +)

- s = s - s; (출력 : -)

- s = s * s; (출력 : *)

- s = s / s; (출력 : /) (s가 0이 아닐 때만 사용 가능)

- s와 t가 같은 경우에는 0

- 바꿀 수 없는 경우에는 -1

- 가능한 방법이 여러 가지라면, 사전 순(*, +, -, /)으로 앞서는 것을 출력

 

해결방법

최소 연산 순서를 구하는 것이기 때문에 BFS로 해결하였다.

계산한 숫자와 이전에 계산했던 연산 기호도 저장해야하므로 클래스를 하나 만들었다. 어떤 연산을 통해 만들어진 숫자인지 연산기호를 저장하기 위한 cal 변수, 만들어진 숫자를 저장하기 위한 num 변수로 이루어진 Calculate 클래스를 만들었다.

큐에 만들어진 Calculate 객체를 저장하였고, 하나씩 꺼내어 숫자를 조합해가면서 목표 t를 찾아나갔다.

이전에 만들었던 숫자인지 체크하기 위해 check boolean 배열을 만들었는데, 얘 때문에 메모리가 많이 잡아먹힌 거 같다.. 메모리 효율을 고려해서 한 번 더 풀어봐야겠다.

 

코드

import java.io.*;
import java.util.*;

// 연산 기호와 숫자를 담을 class
class Calculate{
    String cal;
    long num;

    public Calculate(String cal, long num) {
        this.cal = cal;
        this.num = num;
    }
}

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

        int s = Integer.parseInt(st.nextToken());
        int t = Integer.parseInt(st.nextToken());

	// Calculate 객체들을 담을 queue
        Queue<Calculate> queue = new LinkedList<>();
        // 해당 숫자가 만들어졌던 숫자인지 체크하기 위한 boolean 배열
        boolean[] check = new boolean[1000000001];

	// 첫 s를 큐에 담기
        check[s] = true;
        queue.add(new Calculate("", s));

	// s와 t가 같다면 0 출력
        if(s == t){
            System.out.println(0);
            return;
        }

        while(!queue.isEmpty()){
            Calculate now = queue.poll();		// queue에 담겨있는 것 빼기
            long nowNum = now.num;
            String nowCal = now.cal;
            long mulNum = nowNum * nowNum;		// * 연산
            long plusNum = nowNum + nowNum;		// + 연산
            long minusNum = nowNum - nowNum;		// - 연산

	    // 범위 내에 있고, 방문한 적이 없는 숫자라면
            if(check(mulNum) && !check[(int) mulNum]){
            	// 이전까지 저장된 연산 기호에 현재 연산 기호 추가한 문자열과 숫자로 객체 생성하여 큐에 저장
                queue.add(new Calculate(nowCal+"*", mulNum));
                // 방문 처리
                check[(int) mulNum] = true;
                // 목표 t와 같은 숫자라면
                if(mulNum == t){
                    // 연산기호 출력
                    sb.append(nowCal).append("*");
                    System.out.println(sb);
                    System.exit(0);
                }
            }

	    // 범위 내에 있고, 방문한 적이 없는 숫자라면
            if(check(plusNum) && !check[(int) plusNum]){
            	// 이전까지 저장된 연산 기호에 현재 연산 기호 추가한 문자열과 숫자로 객체 생성하여 큐에 저장
                queue.add(new Calculate(nowCal+"+", plusNum));
                // 방문 처리
                check[(int) plusNum] = true;
                // 목표 t와 같은 숫자라면
                if(plusNum == t){
                    // 연산기호 출력	
                    sb.append(nowCal).append("+");
                    System.out.println(sb);
                    System.exit(0);
                }
            }

	    // 범위 내에 있고, 방문한 적이 없는 숫자라면
            if(check(minusNum) && !check[(int) minusNum]){
            	// 이전까지 저장된 연산 기호에 현재 연산 기호 추가한 문자열과 숫자로 객체 생성하여 큐에 저장
                queue.add(new Calculate(nowCal+"-", minusNum));
                // 방문 처리
                check[(int) minusNum] = true;
                // 목표 t와 같은 숫자라면
                if(minusNum == t){
                    // 연산기호 출력
                    sb.append(nowCal).append("-");
                    System.out.println(sb);
                    System.exit(0);
                }
            }
			
            // '/' 연산은 0이 아닐 때만 사용 가능
            if(nowNum != 0){
                long divNum = nowNum / nowNum;
                
                // 범위 내에 있고, 방문한 적이 없는 숫자라면
                if(check(divNum) && !check[(int) divNum]){
                    // 이전까지 저장된 연산 기호에 현재 연산 기호 추가한 문자열과 숫자로 객체 생성하여 큐에 저장
                    queue.add(new Calculate(nowCal+"/", divNum));
                    // 방문 처리
                    check[(int) divNum] = true;
                    // 목표 t와 같은 숫자라면
                    if(divNum == t){
                        // 연산기호 출력
                        sb.append(nowCal).append("/");
                        System.out.println(sb);
                        System.exit(0);
                    }
                }
            }
        }
		
        // 바꿀 수 없는 경우에는 -1 출력
        System.out.println(-1);

    }
	
    // 범위 내에 존재하는 숫자인지 확인
    static boolean check(long n){
        return n>=1 && n<= 1000000000;
    }
}