개발

[프로그래머스] 키패드 누르기 (자바스크립트) 본문

알고리즘/문제

[프로그래머스] 키패드 누르기 (자바스크립트)

쇼팽리스트 2022. 7. 1. 13:26

LEVEL1 문제치고 엄청 오래 걸렸던 문제다.
2580의 숫자인 경우 bfs를 통해서 왼손과 오른손과의 거리를 구하는 방식으로 했는데.
다른 사람들의 풀이를 보니 케이스가 적어서 그냥 거리를 직접 계산한거를 사용하거나 좀 더 간단하게 구했다.

코드

function solution(numbers, hand) {
    let answer = '';
    const leftBtn = [1,4,7];
    const rightBtn = [3,6,9];
    const graph = [[1,2,3],[4,5,6],[7,8,9],["*",0,"#"]];
    let [leftHand, rightHand] = ["*", "#"];
    let [lpos, rpos] = [[3,0], [3,2]];

    function bfs (a, b, target) {
        let queue = [];
        let visited = new Array(4);
        let dx = [-1,1,0,0];
        let dy = [0,0,-1,1];
        for (let i = 0; i < 4; i++) {
            visited[i] = new Array(3).fill(0);
        }
        queue.push([a, b, 0]);
        visited[a][b] = 1;
        while (queue.length > 0) {
            let [x, y, count] = queue.shift();
            for (let i = 0; i < 4; i++) {
                nx = x + dx[i];
                ny = y + dy[i];

                if (nx < 0 || nx >= 4 || ny < 0 || ny >= 3 || visited[nx][ny] === 1) continue;
                if (graph[nx][ny] === target) return count+1;
                if (graph[nx][ny] !== target) {
                    queue.push([nx, ny, count+1]);
                    visited[nx][ny] = 1;
                }
            }
        }
    } 

    for (let i = 0; i < numbers.length; i++) {
        if (leftBtn.includes(numbers[i]) || numbers[i] === leftHand) {
            leftHand = numbers[i];
            answer += "L";
            continue;
        }
        if (rightBtn.includes(numbers[i]) || numbers[i] === rightHand) {
            rightHand = numbers[i];
            answer += "R";
            continue;
        }

        for (let i = 0; i < 4; i++) {
            for (let j = 0; j < 3; j++) {
                if (graph[i][j] === leftHand) {
                    lpos = [i, j];
                }
                if (graph[i][j] === rightHand) {
                    rpos = [i, j];
                }
            }
        }

        let diff = bfs(lpos[0], lpos[1], numbers[i]) - bfs(rpos[0], rpos[1], numbers[i]);
        if (diff < 0) {
            leftHand = numbers[i];
            answer += "L";
        } else if (diff > 0){
            rightHand = numbers[i];
            answer += "R";
        } else {
            if (hand === "left") {
                leftHand = numbers[i];
                answer += "L";
            } else {
                rightHand = numbers[i];
                answer += "R";
            }
        }

    }
    return answer;
}