[백준] 14395 4연산

www.acmicpc.net/problem/14395

14395번: 4연산

2020-11-22

---

import java.util.HashSet;
import java.util.LinkedList;
import java.util.Queue;
import java.util.Scanner;
 
class Temp {
    long num;
    String str;
    public Temp(long num, String str) {
        this.num = num;
        this.str = str;
    }
}
 
public class Main14395 {
    public static long S, T;
    public static String answer;
    public static Queue<Temp> q;
    public static HashSet<Long> set;
    
    public static void solve() {
        set = new HashSet<>();
        loop:while(!q.isEmpty()) {
            Temp tmp = q.poll();
            long num = tmp.num;
            String str = tmp.str;
            
            for(int i = 0; i < 4; i++) {
                long nx = 0;
                String nstr = "";
                switch(i) {
                case 0: // *
                    nx = num * num;
                    nstr = str + "*";
                    break;
                case 1: // +
                    nx = num + num;
                    nstr = str + "+";
                    break;
                case 2: // -
                    nx = num - num;
                    nstr = str + "-";
                    break;
                case 3: // /
                    if(num != 0) {
                        nx = num / num;
                        nstr = str + "/";
                        if(!set.contains(nx)) {
                            set.add(nx);
                            q.add(new Temp(nx, nstr));
                        }
                    }
                    break;
                }
                if(i != 3 && !set.contains(nx)) {
                    set.add(nx);
                    q.add(new Temp(nx, nstr));
                }
                    
                if(nx == T) {
                    answer = nstr;
                    break loop;
                }
            }
        }
    }
    
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        S = sc.nextLong();
        T = sc.nextLong();    
        answer = "";
 
        if(S == T) answer = "0";
        else {            
            q = new LinkedList<Temp>();
            q.add(new Temp(S, ""));
            solve();
        }
        
        if(answer == "") System.out.println("-1");
        else System.out.println(answer);
    }
}
 

 

1. S와 T가 같은 경우 바로 답을 출력하고 그런 경우가 아니라면 탐색을 시작한다. queue에 long S와 String 빈 값을 갖고 시작했다.

 

2. queue에 들어간 값을 빼면서 각각 *, +, -, / 순서로 값을 계산해본다. 이 순서로 계산을 한 이유는 가능한 방법이 여러 가지라면, 사전 순으로 앞서는 것을 출력한다. 라는 문구가 있었기 때문이다. 애초에 연산자 아스키 코드 순서대로 계산을 하면 나중에 후처리를 할 피요가 없다.

 

3. 계산을 하면서 한 번도 도출해본적이 없는 결과값이면 HashSet에 저장하고 queue에 저장을 하였다.

10^9이기 때문에 O(1000000000)로 시간초과가 날 수 밖에 없다. 그래서 HashSet을 사용하여 중복을 제거 해줬다.