[프로그래머스] 숫자 변환하기 Java 풀이

 

첫 번째 풀이

exists를 사용하지 않으면 시간초과가 뜬다. 이전에 한번이라도 큐에 들어갔던 숫자면 skip.

Node 를 쓰고싶지 않았는데, 다른 방법이 생각나지 않아서 사용했다. 밑에 풀이에선 배열로 수정됨

import java.util.*;

public class Main {
    public static void main(String[] args) {
        int res = solution(2, 5, 4);
        System.out.print(res);
    }

    public static int solution(int x, int y, int n) {
        if (x == y)
            return 0;

        Queue<Node> queue =  new LinkedList<>();
        int[] exists = new int[1000001];

        queue.add(new Node(x,1));
        exists[x] = 1;

        while(!queue.isEmpty()) {
            Node node = queue.poll();

            int tmp = node.x + n;
            int tmp2 = node.x * 2;
            int tmp3 = node.x * 3;

            int res = node.res;

            if (tmp == y || tmp2 == y || tmp3 == y) {
                return res;
            }

            if(tmp < y && exists[tmp] == 0) {
                queue.add(new Node(tmp,res+1));
                exists[tmp] = 1;
            }

            if(tmp2 < y && exists[tmp2] == 0) {
                queue.add(new Node(tmp2,res+1));
                exists[tmp2] = 1;
            }

            if(tmp3 < y && exists[tmp3] == 0) {
                queue.add(new Node(tmp3,res+1));
                exists[tmp3] = 1;
            }
        }

        return -1;
    }
}

class Node {
    int x;
    int res;
    Node(int x, int res) {
        this.x = x;
        this.res = res;
    }
}

 

 

다른 사람의 풀이를 보면서 생각한 최종 풀이

Node class를 없애고, exists 배열로 처리했다.

import java.util.*;

public class Main {
    public static void main(String[] args) {
        int res = solution(2, 5, 4);
        System.out.print(res);
    }

    public static int solution(int x, int y, int n) {
        if (x == y)
            return 0;

        Queue<Integer> queue =  new LinkedList<>();
        int[] exists = new int[1000001];

        queue.add(x);
        exists[x] = 1;

        while(!queue.isEmpty()) {
            int node = queue.poll();

            int tmp = node + n;
            int tmp2 = node * 2;
            int tmp3 = node * 3;

            int res = exists[node];

            if (tmp == y || tmp2 == y || tmp3 == y) {
                return res;
            }

            if(tmp < y && exists[tmp] == 0) {
                queue.add(tmp);
                exists[tmp] = res+1;
            }

            if(tmp2 < y && exists[tmp2] == 0) {
                queue.add(tmp2);
                exists[tmp2] = res+1;
            }

            if(tmp3 < y && exists[tmp3] == 0) {
                queue.add(tmp3);
                exists[tmp3] = res+1;
            }
        }

        return -1;
    }
}

 

 

배운점

큐나 스택만 보면 자꾸 Node 클래스를 생각하는 습관을 고쳐야 할 것 같다.

배열을 사용하는 방향으로 생각해봐야겠다.