[백준] 14395번 4연산

생각

Github - https://github.com/hellojdh/Code/blob/master/src/baekjoon/q10000/Q14395.java

바꿀 숫자 S와 목표 숫자 T가 주어진다. * + - / 를 해서 S에서 T로 바꿀 수 있다면 사용한 연산자들을
출력하고 바꿀 수 없다면 -1을 S와 T가 동일하게 주어진다면 0을 출력하여라.
연산자로 바꾼다는 것은 다음을 의미한다.
+   : S = S+S
*    : S = S*S
-    : S = S-S
/    : S = S/S

처음 생각

처음 문제를 봤을 때, "왜이렇게 정답률이 낮지?"라는 생각을 했었다. 그리고 풀고나서는 정답률을 낮추는데 기여했다.

▶ 매번 틀릴때마다드는 생각이지만 문제를 잘읽어야한다.

다음 생각

S에서 T로 바꾸기가 가능하다면 최소의 연산 개수로 바꿔주어야하므로 BFS 탐색을 이용하였다. 그리고 가능한 것들의 연산 개수가 같다면 * + - / 순으로 정렬했을 때, 가장 앞에오는 순서대로 바꿔주어야한다.

▶ 우선, 사용한 연산자들을 출력해야하므로 String 값으로 연산자들을 더해주었다.

▶ 탐색을 위해 queue에 집어넣을 때 * + - / 순으로 집어넣어주면 자연스럽게 먼저 되는 것이 가장 빠른 순서가 된다.

다다음 생각

제출을 했다. 메모리를 초과하였다!! 문제를 보니 S와 T의 범위가 최대 10^9 = 10억 이다. 중복된 숫자를 다시 검사할 필요는 없으므로 방문 배열의 범위를 넉넉하게 2*(S+T)+1로 만들어 주었었는데 이게 문제였다. 크기가 20억인 배열이라니!

▶ 배열로는 체크를 못한다 생각하여 HashSet<String>을 사용해서 방문 체크를 해주었다.

▶ 그래도 틀렸습니다!

다다다음 생각

문제 풀이에 문제가 있나 생각을 해보면서 혹시 가능한 횟수가 여러개일 때가 문제인가? 생각해서 바꿔보고 제출하니 또 틀렸습니다가 나왔다. 또 조금 고쳐보고 틀렸습니다. 이제는 모르겠다 할 때, 범인은 가까이있었다.

▶ 크기가 커서 배열을 바꿨었다. 즉, int형으로는 숫자 받는것까지는 문제가 안되지만 연산을 하는 과정에서 오버플로우가 발생했을 것이다.

▶ long 형으로 바꾸고 제출하니 통과하였다.

방안

1) 시간 복잡도를 생각하면서 풀기(시간이 빡빡하다면)
2) 문제에 주어진 범위를 생각하기

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59

package baekjoon.q10000;   import java.util.HashSet; import java.util.LinkedList; import java.util.Queue; import java.util.Scanner;   public class Q14395 {     static long s,t;     public static void main(String[] args) {         Scanner sc = new Scanner(System.in);         s = sc.nextLong();         t = sc.nextLong();         if(s==t) System.out.println(0);         else System.out.println(solve());     }          static HashSet<Long> set = new HashSet<>();     // 우선 순위는 * + - /     private static String solve() {         Queue<Pair> queue = new LinkedList<>();         queue.add(new Pair(s, ""));         set.add(s);         while(!queue.isEmpty()) {             Pair n = queue.poll();             if(n.n==t) {                 return n.cal;             }             for(int i=0;i<4;i++) {                 long tN = cal(n.n,i);                 if(tN<1) continue;                 if(set.contains(tN)) continue;                 set.add(tN);                 queue.add(new Pair(tN, n.cal+dir[i]));             }         }         return "-1";     }          static String[] dir = {"*","+","-","/"};     private static long cal(long n,int sw) {         switch (sw) {         case 0: return n*n;         case 1: return n+n;         case 2: return n-n;         case 3: return n/n;         }         return 0;     }          static class Pair{         long n;         String cal;         Pair(long n,String cal){             this.n= n;             this.cal = cal;         }     } }