[programmers] 숫자 변환하기

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

프로그래머스

 

---

< 숫자 변환하기 >

 

문제 풀이 (Java)

import java.util.*;

class Solution {
	public int solution(int x, int y, int n) {
		int answer = -1;

		Queue<int[]> queue = new LinkedList<>();
		queue.add(new int[] { x, 0 });

		boolean visited[] = new boolean[y + 1];
		visited[x] = true;

		if (x == y) {
			answer = 0;
		} else {
			while (!queue.isEmpty()) {
				int info[] = queue.poll();

				if (info[0] + n == y || info[0] * 2 == y || info[0] * 3 == y) {
					answer = info[1] + 1;
					break;
				}

				if (info[0] + n < y && !visited[info[0] + n]) {
					queue.add(new int[] { info[0] + n, info[1] + 1 });
					visited[info[0] + n] = true;
				}
				if (info[0] * 2 < y && !visited[info[0] * 2]) {
					queue.add(new int[] { info[0] * 2, info[1] + 1 });
					visited[info[0] * 2] = true;
				}
				if (info[0] * 3 < y && !visited[info[0] * 3]) {
					queue.add(new int[] { info[0] * 3, info[1] + 1 });
					visited[info[0] * 3] = true;
				}
			}
		}
		return answer;
	}
}

 

Queue에 x와 연산 횟수 0을 추가한다. 만약 x와 y가 같다면 answer에 0을 저장하고, 같지 않다면 Queue가 빌 때까지 다음 과정을 반복한다.

 

1. queue poll

2. n을 더하거나, 2를 곱하거나, 3을 곱한 값이 y라면 answer에 횟수를 업데이트하고 종료

3. n을 더한 값이 y보다 작고 아직 한 번도 나오지 않은 값이라면 queue에 저장 및 방문 표시

4. 2를 곱한 값이 y보다 작고 아직 한 번도 나오지 않은 값이라면 queue에 저장 및 방문 표시

5. 3을 곱한 값이 y보다 작고 아직 한 번도 나오지 않은 값이라면 queue에 저장 및 방문 표시

 

최종 answer을 반환한다.  

 

---

---

 

출처: 프로그래머스 코딩 테스트 연습, 
https://school.programmers.co.kr/learn/challenges