[프로그래머스] Level2 - 숫자 변환하기(Javascript)

프로그래머스

▶ 문제 요약

1. 자연수 x를 y로 변환하려고 한다.

2. 사용할 수 있는 연산 (1) x에 n을 더한다 (2) x에 2를 곱한다 (3) x에 3을 곱한다.

3. 최소 연산 횟수를 return하고 만들 수 없으면 -1을 return하세요.

 

▶ 코드

function solution(x, y, n) {
    // x를 y로 만들 수 없는 경우 고려 -1이 기본값
    let answer = -1;
    // queue에 [목표값, 횟수]
    let queue = [[y, 0]];
    // 방문한 곳을 재방문하지 않기 위해 Set()함수 활용
    let visited = new Set([y]);
    
    while (queue.length > 0) {
    
    	// [목표값, 횟수] 빼기
        let [now, count] = queue.shift();
        
        // 만약 현재 값이 우리가 변환하기 위한 값과 일치하면 정답 및 종료
        if (now === x) {
            answer = count;
            break;
        
        }
        
        // 사용할 수 있는 연산 하향식 접근
        const way = [now - n, now / 2, now / 3];
        

        for (const w of way) {
        
            // 음수거나 혹은 정수형이 아닌 경우에는 무시
            if (w < 0 || !Number.isInteger(w)) continue;
            
            // 방문한적이 없으면 방문처리 및 queue에 다음 값을 넣기
            if (!visited.has(w) {
            	visited.add(w);
                queue.push([w, count+1]);
            
            }
        
        }
    
    
    }
    return answer;
    


}

▶ 풀이 과정

1. 나는 이 문제에서 최단 경로를 보장하는 BFS의 특성을 고려해서 최소 연산 횟수를 구할 수 있다고 판단해서 BFS 알고리즘을 선택했다. 일단 문제에서 x를 y로 만들 수 없다면 -1을 리턴해야하니까 정답 변수를 -1로 시작하겠다.

 

2. 원래는 상향식으로 접근 즉 10이 40이 되는 연산 횟수인데 반대로 하향식으로 40이 10이 되는 연산 횟수를 구하는 방법을 사용했다. 

그래서 queue에 x가 아닌 y를 넣었고 연산 횟수를 세어줄 변수를 같이 담아준다.

 

3. 방문한 곳을 재방문하지 않기 위해서 방문처리를 해야하는데 Set()함수를 사용했다. 

 

4. queue가 있을때까지 돌면서 queue에 들어있는 원소(연산해야할 값, 연산 횟수)를 shift()메소드로 빼준다.

 

5. 만약에 도달해야하는 숫자에 도달하면 이제까지의 연산횟수를 정답에 담아주고 종료한다.

 

6. 그게 아니면 세 가지 연산을 사용해서 계산한다. 하향식 접근이다보니 기존에 상향식 [now + n, now * 2, now * 3]에서 더하거나 곱했는데 반대로 빼거나 나눴다. 

 

7. 세 가지의 방법으로 연산한 값을 돌면서 음수거나 정수가 아닌 경우에는 무시한다. 

 

8. 양수이거나 정수인 경우 중에 방문한 적이 없는 경우 즉, w라는 값이 Set()에 존재하는지 확인해서 없는 경우

 

9. Set()에 넣어주고 다음 값을 순회하기 위해서 queue에 [계산된 값, 연산 횟수 +1]을 넣어준다.

 

10. return해준다.

 

▶ 배운점

1. 방문표시 할 때 Set()함수를 적극적으로 활용하자. 

 

2. 어떤 수에 도달하는 문제일때 상향식 접근 말고 하향식 접근도 고려해보자