프로그래머스 [Lv. 2] 숫자 변환하기 {언어 : JavaScript} [성능 개선 필요]

문제 링크

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

프로그래머스

 

정답 코드

function solution(x, y, n) {
    let visited = Array(1000001).fill().map(() => -1);
    
    const q = [x];
    visited[x] = 0;
    while (q.length) {
        const cv = q.shift();
        if (cv >= y) {
            continue;
        };
        const visitedCV = visited[cv] + 1;
        
        if (visited[y] != -1 && visitedCV >= visited[y]) {
            continue;
        };
        
        const cv3 = cv * 3;
        if (cv3 <= y) {
            if (visited[cv3] == -1 || visited[cv3] > visitedCV) {
                q.push(cv3);
                visited[cv3] = visitedCV;
            };
        };
        
        const cv2 = cv * 2;
        if (cv2 <= y) {
            if (visited[cv2] == -1 || visited[cv2] > visitedCV) {
                q.push(cv2);
                visited[cv2] = visitedCV;
            };
        };
        
        const cvn = cv + n;
        if (cvn <= y) {
            if (visited[cvn] == -1 || visited[cvn] > visitedCV) {
                q.push(cvn);
                visited[cvn] = visitedCV;
            };
        };
    };
    
    const answer = visited[y];
    return answer;
}

풀이 방법

• 방문 배열 만들어서 중복을 제거하고 3 가지 경우로 나눠서 bfs를 돌렸다.
• 가지치기로 이미 y를 찾았는데 y를 찾은 값 보다 작을 경우 탐색을 더 못하게 continue를 해줬다.

느낀점

• 통과는 했습니다만... 다시 풀어봐야겠죠?