[프로그래머스][자바스크립트][Level1][카카오] 키패드 누르기

풀이

 

 

/**
 * 키패드누르기.js
 * https://programmers.co.kr/learn/courses/30/lessons/67256?language=javascript
 */

function solution(numbers, hand) {
    let currLeft = "*", currRight = "#";
    let answer = "";

    numbers.forEach((num) => {
        const rule = staticRule(num);

        if (rule) {
            answer += rule;
            if (rule === "L") {
                currLeft = num;
            } else {
                currRight = num;
            }
        } else {
            const fromLeft = BFS(graph, currLeft, num);
            const fromRight = BFS(graph, currRight, num);

            if (fromLeft === fromRight) {
                if (hand === "left") {
                    answer += "L";
                    currLeft = num;    
                } else {
                    answer += "R";
                    currRight = num;
                }
            } else if (fromLeft < fromRight) {
                answer += "L";
                currLeft = num;
            } else {
                answer += "R";
                currRight = num;
            }
        }
    });

    return answer;
}

function staticRule(num) { 
    switch (num) {
        case 1:
        case 4:
        case 7:
            return "L";
        case 3:
        case 6:
        case 9:
            return "R";
        default:
            return null;
    }
}

const graph = {
    1: [2, 4],
    2: [1, 3, 5],
    3: [2, 6],
    4: [1, 5, 7],
    5: [2, 4, 6, 8],
    6: [3, 5, 9],
    7: [4, 8, "*"],
    8: [5, 7, 9, 0],
    9: [6, 8, "#"],
    0: [8, "*", "#"],
    "*": [7, 0],
    "#": [9, 0]
};

function BFS(graph, startNode, targetNode) {
    const visited = []; 
    let needVisit = [], answer = Infinity; 
    needVisit.push({distance: 0, node: startNode}); 
    while (needVisit.length > 0) {
        const { distance, node } = needVisit.shift();
        if (visited.indexOf(node) === -1) {
            visited.push(node);
            const newNeedVisit = graph[node].map((n) => {
                return { distance: distance + 1, node: n };
            });
            needVisit = [...needVisit, ...newNeedVisit];
        }
        if (node === targetNode) {
            answer = distance;
            break;
        }
    }
    return answer;
};

 

1, 4, 7 은 왼손, 3, 6, 9는 오른손으로 누르는건 고정된 규칙이라 staticRule 함수에서 처리해준다. 

 

위에 나온 숫자 이외의 숫자를 눌렀을 때는 왼손과 오른손 중 가까운 손으로 누르되, 거리가 동일한 경우 주로 사용하는 손으로 누른다. 

이 때는 각 키패드를 그래프의 노드로 취급해서 눌러야하는 번호를 목표 노드로, 왼손과 오른손의 위치를 각각 시작 노드로 설정한 뒤 BFS를 통해 왼손에서와 오른손에서의 최소 거리를 구하는 방식으로 접근했다. 왼손과 오른손으로부터의 최소거리를 구하고 난 뒤엔 주어진 조건대로 로직을 짜주면 끝난다.