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

 

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

프로그래머스

 

이 문제는 정답까지 필요한 최소 연산 수를 구하는 문제이다.

 

그래서 처음 생각해낸 알고리즘 방법은 bfs였다.

 

문제를 풀기 앞서 먼저 과정을 생각해보자.

// 1차 고민
1. y값과 x값을 비교한다.
2. 같지 않으면 연산한다.
3. 연산값이 y를 넘어서면 답이 일치하는것이 없으므로 종료한다.

// 2차 고민
1. bfs로 스택에 넣어서 관리한다.
2. 중복연산을 피하기 위해 visited를 set로 관리한다.
3. 최소연산 값을 구하기위해 count를 사용한다.

// 3차 고민
1. bfs와 스택을 사용해 반복문을 작성할때, 너비값을 찾아서 2중 반복으로 돌린다.
2. 이렇게 하는 이유는 최소연산값을 구하기 위해서이다.
예) 스택에 들어가 있는 숫자들을 너비의 척도로 사용하자
a, b, c라는 분기가 각 노드마다 존재한다고 가정하자.

최소연산이 1일때,
큐 = { a, b, c } 이므로 너비는 3이다.

최소연산이 2일때,
큐 = { a-a, a-b, a-c, b-a, b-b, b-c, c-a, c-b, c-c}이므로 너비는 9이다.

3. 큐에 값을 집어넣을때 조건을 생각해보자. 
   visited에 있는 숫자의 집합과 비교후 포함되어 있지 않아야한다.
   연산값이 y보다 작아야한다.

 

이를 고려하고 아래와 같이 코드를 작성했다. 

import java.util.*;

class Solution {
    public int solution(int x, int y, int n) {
        int answer = 0;
        Queue<Integer> q = new LinkedList<>();
        Set<Integer> visited = new HashSet<>();
        
        q.add(x);
        visited.add(x);
        
        while (!q.isEmpty()) {
            int size = q.size();
            for (int i = 0; i < size; i++) {
                int qq = q.poll();
                if(qq == y ) {
                    return answer;
                }
                if ( qq + n <= y && !visited.contains(qq + n)) {
                    q.add(qq + n);
                    visited.add(qq + n);
                }
                if ( qq * 2 <= y && !visited.contains(qq * 2)) {
                    q.add(qq * 2);
                    visited.add(qq * 2);
                }
                if ( qq * 3 <= y && !visited.contains(qq * 3)) {
                    q.add(qq * 3);
                    visited.add(qq * 3);
                }
            }
                answer++;
            
        }
        
        return -1;
    }    
}

 

스택이 다 돌았을때에도 qq가 y와 같지 않다면, 이는 연산을 어떻게해도 y와 같을수 없다느 뜻이므로 while문이 종료될때 -1을 리턴하도록 했다.

 

bfs라는 개념을 익히기에는 아주 좋은 문제인것 같다.