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

문제를 보자마자 해당문제는 x에서 y에 도달하게끔 만드는 문제이다.

x에서 y로가는 최단방법을 찾으면 된다고 생각했고,

그래서 알고리즘중에서 많은 양의 데이터 중 원하는 데이터를 찾는 탐색에 적합한 BFS(너비 우선 탐색)가 떠올랐다.

BFS의 탐색 플로우는 그래프나 트리 등의 자료 구조에서 가까운 노드부터 탐색하는 알고리즘이다.

이 알고리즘은 큐를 사용하여 탐색해야 할 노드들을 저장하고, 먼저 저장된 노드부터 순서대로 탐색한다.

이때, 탐색한 노드들을 방문했음을 표시하여 중복 방문을 방지한다.

1. 초기화: 시작 노드를 큐에 넣고, 시작 노드를 방문했음을 표시한다.

2. 큐가 비어있지 않은 동안 반복:

-큐에서 노드를 하나 꺼낸다.

-해당 노드에 인접한(연결된) 노드들 중 방문하지 않은 노드를 큐에 추가하고 방문했음을 표시한다.

-큐가 빌 때까지 반복: 큐가 빈상태가 되면 모든 노드에 대한 탐색이 종료된다.

위의 방법을 사용하여 알고리즘적 사고를 해보았다.

먼저 문제에서 주어진 연산은 x에 n을 더하는 것, x를 2배로 곱하는 것, x를 3배로 곱하는 것이다.

우선, BFS를 위해 큐와 방문한 숫자를 추적하기 위한 집합을 초기화했다.

그런 다음 큐에 초기 상태인(현재 숫자,작업 수)를 추가한다. 이때, 방문한 숫자를 표시한다.

큐가 비어있지 않은 동안에는 다음 작업을 수행한다.

1. 현재 숫자가 y와 같은지 확인한다. 같다면 작업 수를 return

2. 현재 숫자에 n을 더하는 경우를 확인한다. 결과가 y보다 작거나 같고 방문한 숫자가 아니라면 큐에 추가하고 방문한 숫자로 표시한다.

3. 현재 숫자를 2배로 곱하는 경우를 확인한다. 결과가 y보다 작거나 같고 방문한 숫자가 아니라면 큐에 추가하고 방문한 숫자로 표시한다.

만약 y에 도달할 수 없는 경우 -1을 return한다.

 

결과적으로 코드는 아래와 같이 작성했다.

import java.util.*

class Solution {

    fun solution(x: Int, y: Int, n: Int): Int {
        // x가 이미 y와 같다면 작업이 필요하지 않음
        if (x == y) return 0 
        
        // BFS에 사용할 큐로 LinkedList 사용
        val queue = LinkedList<Pair<Int, Int>>() 
        // 방문한 숫자를 추적하기 위한 집합
        val visited = mutableSetOf<Int>() 
        
        // 초기 상태를 큐에 넣음: (현재 숫자, 작업 수)
        queue.offer(Pair(x, 0)) 
         // x를 방문한 것으로 표시
        visited.add(x)
        
        // 큐가 비어있지 않은 동안 반복
        while (queue.isNotEmpty()) { 
            
            //current: 현재 탐색 중인 노드/ operations:그 노드까지의 작업 수
            val (current, operations) = queue.poll() // 큐에서 요소를 꺼내옴
            
            if (current == y) return operations // y에 도달하면 작업 수를 반환
            
            // 현재 숫자에 n을 더함
            val addResult = current + n
            if (addResult <= y && addResult !in visited) { // y를 넘지 않고, 방문하지 않은 숫자인 경우
                queue.offer(Pair(addResult, operations + 1)) // 큐에 추가하고 작업 수를 1 증가시킴
                visited.add(addResult) // 방문한 숫자로 표시
            }
            
            // 현재 숫자를 2배로 곱함
            val multiplyBy2Result = current * 2
            // y를 넘지 않고, 방문하지 않은 숫자인 경우
            if (multiplyBy2Result <= y && multiplyBy2Result !in visited) { 
                queue.offer(Pair(multiplyBy2Result, operations + 1)) // 큐에 추가하고 작업 수를 1 증가시킴
                visited.add(multiplyBy2Result) // 방문한 숫자로 표시
            }
            
            // 현재 숫자를 3배로 곱함
            val multiplyBy3Result = current * 3
             // y를 넘지 않고, 방문하지 않은 숫자인 경우
            if (multiplyBy3Result <= y && multiplyBy3Result !in visited) {
                queue.offer(Pair(multiplyBy3Result, operations + 1)) // 큐에 추가하고 작업 수를 1 증가시킴
                visited.add(multiplyBy3Result) // 방문한 숫자로 표시
            }
        }
        // y에 도달할 수 없는 경우 -1을 반환
        return -1 
    }
}

결과는 성공적이었고,

알고리즘을 또다시 복습할 수 있어서 좋은 기회였다.