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

문제

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

프로그래머스

 

해결방안

문제에서 "최소 연산 횟수"를 구하라고 했으므로 BFS로 풀어야 된다.

=> 문제에서 "최소~" 구하라는 말이 나오면 BFS로 풀어야 하는구나라고 생각하면 된다.

 

BFS를 구하기 위해서는 3가지 배열이 필요하다.

1. queue 배열 : 해당 위치에서 부터 다음 지점으로 갈 수 있는 곳의 위치를 넣어주는 곳
2. ch 배열 : 내가 갔던 위치 체크하는 곳 (중복으로 가지 못하게 하기 위해)
   • 안지나 갔으면 0, 지나갔으면 1로 표시
3. dis 배열 : 해당 위치에 갔을 때 최소 몇 번 움직여서 갔는지 체크하는 곳 (레벨 표시하는 곳)

이렇게 쓰면 잘 이해가 안되니 입출력 예 #1을 예시로 알아보자

입출력 예 # 1

x	y	n	result
10	40	5	2

 

초기화 : x = 10

• queue = [10]
• ch[10] = 1
• dis[10] = 0

현재 위치 = 10

• queue = [15, 20, 30]
• ch[15] = 1, ch[20] = 1, ch[30] = 1
• dis[15] = 1, dis[20] = 1, dis[30] = 1

현재 위치 = 15

• queue = [20, 30]
• 변동 없음
  • 15+5 = 20 : 이미 지나갔던 숫자 (이미 ch에 체크되어 있음)
  • 15*2 = 30 : 이미 지나갔던 숫자 (이미 ch에 체크되어 있음)
  • 15*3 = 45 : y보다 큰 숫자 임으로 필요 없는 숫자

현재 위치 = 20

• queue = [30, 25, 40]
  • ch[25] = 1, ch[40] = 1
  • dis[25] = 2, dis[25] = 2

여기서 40을 구했기 때문에 끝남

 

 

정답

// 최소 횟수 임으로 BFS로 구해야 된다.
function solution(x, y, n) {
    if(x==y) return 0; // 이거 안하면 테스트 6 통과 못 함
    
    // x <= y임으로 ch, dis배열을 0~y로 했다.
    let ch = Array.from({length: y+1}, () => 0);
    let dis = Array.from({length: y+1}, () => 0);
    let queue = [];
    
    // x의 값 queue, ch, dis에 표시해두기
    queue.push(x);
    ch[x] = 1;
    
    // 빈 queue이면 구할 수 있는 모든 방법을 구했다는 의미
    while(queue.length){
        let nowNum = queue.shift(); // 큐에서 뺀 값이며 현재 위치
        
        // 사용할 수 있는 연산 종류는 3가지 임으로 for of문으로 담아줌
        for(let i of [nowNum + n, nowNum * 2, nowNum * 3]){
            if(i === y) return dis[nowNum] + 1; // 답을 찾을 경우 최소횟수 리턴
            
            // x보다 크고, y보다 작거나 같고 체크되어 있지 않을 경우(i<y && ch[i]===0 충분)
            if(i > x && i <= y && ch[i] === 0) {
                ch[i] = 1; // 현재위치 체크해주고
                queue.push(i); // 현재위치에서 갈 수 있는 위치 넣어주고
                dis[i] = dis[nowNum] + 1; // 현재위치의 최소횟수를 넣어준다.
            }            
        }
    }
    return -1; // while문이 끝난다는 건 y로 변환하지 못한다는 의미임으로 -1 출력
}