프로그래머스 Java Lv2 숫자 변환하기

 

https://school.programmers.co.kr/learn/courses/30/lessons/154538#

 

해당 문제는 Queue를 이용하여 해결하였다.

x를 y로 변환하기 위한 "최소 연산 횟수"를 계산해야 하므로 Queue를 이용하여

x에 "n 을 더하기, 2를 곱하기, 3을 곱하기" 3가지 연산을 하고 Queue에 넣는 방식을 취했다.

 

Queue에 값을 넣을 때는 해당 값이 몇 번 연산된 값인지 표기하기 위해 int[] 를 사용하여 값과 연산 횟수를 같이 저장하였다.

그리고 가장 먼저 y와 같아지는 경우의 시행 횟수를 return 하도록 하였다.

 

"Queue를 사용하므로 가장 처음 같아지는 경우가 최소 연산 횟수이다."

만약 같아 지는 경우가 없다면, 변환이 불가능한 경우이므로 -1 를 return 한다.

 

하지만 단순히 x 값에 대해 3가지 연산을 하고 Queue에 넣는 방식만 사용했을 경우, 몇몇 케이스에서 시간초과가 발생하였다.

 

시간초과 코드

import java.util.Queue;
import java.util.LinkedList;

class Solution {
    public int solution(int x, int y, int n) {
        Queue<int[]> que = new LinkedList<>();
        que.add(new int[]{x, 0});
        
        while (!que.isEmpty()) {
            int[] tmp = que.poll();
            int num = tmp[0];
            int cnt = tmp[1];

            if (num > y) continue;

            if (num == y) {
                return cnt;
            } else {
                cnt++;
                que.add(new int[]{num + n, cnt});
                que.add(new int[]{num * 2, cnt});
                que.add(new int[]{num * 3, cnt});
            }
        }
        return -1;
    }
}

 

속도 개선을 위하여 HashSet을 추가하여 값의 중복을 체크하는 로직을 추가했다.

 

Queue에 값을 넣기 전, HashSet에 값이 있는지 확인한다.

만약 이미 HashSet에 값이 들어있다면 그 값은 이미 더 적거나 같은 시행횟수로 계산되었기 때문에 Queue에 넣지 않는다.

 

개선 코드

import java.util.Queue;
import java.util.LinkedList;
import java.util.HashSet;

class Solution {
    public int solution(int x, int y, int n) {
        Queue<int[]> que = new LinkedList<>();
        HashSet<Integer> distinct = new HashSet<>();
        
        que.add(new int[]{x, 0});
        
        while (!que.isEmpty()) {
            int[] tmp = que.poll();
            int num = tmp[0];
            int cnt = tmp[1];

            if (num > y) continue;

            if (num == y) {
                return cnt;
            } else {
                cnt++;
                if (!distinct.contains(num + n)) {
                    distinct.add(num + n);
                    que.add(new int[]{num + n, cnt});
                }
                if (!distinct.contains(num * 2)) {
                    distinct.add(num * 2);
                    que.add(new int[]{num * 2, cnt});
                }
                if (!distinct.contains(num * 3)) {
                    distinct.add(num * 3);
                    que.add(new int[]{num * 3, cnt});
                }
            }
        }
        return -1;
    }
}