[프로그래머스-JS] level.1 키패드 누르기

https://programmers.co.kr/learn/courses/30/lessons/67256

코딩테스트 연습 - 키패드 누르기

 

풀이

처음에는 if문으로 1,4,7 / 3,6,9를 나누고  2,5,8,0은 따로 해줬는데 이렇게 하면 너무 if문이 많아져서 

질문하기에서 약간의 힌트를 얻었다. 

힌트를 보기전에는 1~12번 캐이스는 전부 성공하는데  13~20번은 전부 실패하였다. 

그 이유는  이 문제에서 상하좌우로 이동은 제한했기 때문이다. 

예를 들어  

눌러야하는 수가 8

왼손의 현재위치가 4

오른손의 현재위치가 2 

그리고 오른손 잡이일때 

왼손 오른손 둘다 이동거리가 "2"이기 때문에  

결장하는 데 중요한 것은 무슨 손 잡이인지이다

이 경우 오른손 잡이 이기때문에 오른손이 2에서 8로 이동해야한다. 

하지만 그냥 거리 계산으로 구한다면 왼쪽이 움직일 것이다. 

우리가 일반적으로 길이를 구할때 쓰는 공식은 최단거리 구할때 쓰는 것이다 쉽게말하면

 

 

초록색이 바로 최단거리 우리가 일반적으로 점과 점사이 거리를 구할때 쓰는 공식인 유클리드 기하학이고 

빨간색 파란색 노란색은  택시 기하학(맨하튼 거리)라고 부르는 두 점사이의 거리이다. 

이 문제에서는 상하좌우로만 이동이 가능하기에 이 택시시하학을 사용해서 문제를 풀어야한다. 

"상하좌우"에서 눈치를 챘어야하는데 왜 그러지 못했을까 ..

 

나의 코드

function solution(numbers, hand) {
    var answer = '';
    var LlocalX = 0;
    var LlocalY = 0;
    var RlocalX = 2;
    var RlocalY = 0;
    const nums = {
            1: [0,3],
            2: [1,3],  
            3: [2,3],  
            4: [0,2],  
            5: [1,2],  
            6: [2,2],  
            7: [0,1], 
            8: [1,1],  
            9: [2,1], 
            "*":[0,0],  
            0: [1,0], 
            "#":[2,0],    

    }
    
    for(i=0 ; i < numbers.length ; i++){
        let num = numbers[i];
        if(num === 1 || num === 4 || num === 7){
            answer += "L"
            LlocalX = nums[num][0]
            LlocalY = nums[num][1]
        }else if(num === 3 || num === 6 || num === 9){
            answer += "R"
            RlocalX = nums[num][0]
            RlocalY = nums[num][1]
        }else{
            let LD = Math.abs(+nums[num][0] - +LlocalX) + Math.abs(+nums[num][1] - +LlocalY)
            let RD = Math.abs(+nums[num][0] - +RlocalX) + Math.abs(+nums[num][1] - +RlocalY)

            if(LD > RD){
                answer += "R"
                RlocalX = nums[num][0]
                RlocalY = nums[num][1]
            }else if(LD < RD){
                answer += "L"
                LlocalX = nums[num][0]
                LlocalY = nums[num][1]
            }else{
                if(hand === "right"){
                    answer += "R"
                    RlocalX = nums[num][0]
                    RlocalY = nums[num][1]
                }else{
                    answer += "L"
                    LlocalX = nums[num][0]
                    LlocalY = nums[num][1]
                }
            }
        }
    }  
    return answer;
}

일단 택시기하학을 사용해야겠다 생각을 하고 

좌표지정먼저 했다. 

"*" 표시를 기준으로 임의의 좌표를 설정해주고 객체안에 넣어줬다. 

그리고 1,4,7은 어차피 왼손밖에 못 누르고 3,6,9는 오른손밖에 못 누르니 따로 나눠주고 위치만 저장시켰다 

그리고 나머지 2,5,8,0 일때만 택시시하학을 사용하면 되었다. 

 

 

다른 사람 풀이

 

function solution(numbers, hand) {
    let answer = '';
    // imagine a grid, and assign each number coordinates
    // by taking 5 being 0,0.
    // If needed, this can also be done programmatically.
    const grid = [[0,-2], [-1,1], [0,1],
                  [1,1], [-1,0], [0,0],
                  [1,0], [-1,-1], [0,-1],
                  [1,-1], [-1,-2], [1,-2]];
    let L = 10; // 10th element of the grid are * and # of the keypad
    let R = 11; // 11th
    let L_steps, R_steps; 
    hand = hand[0].toUpperCase();
    numbers.forEach(el => {
        switch (grid[el][0]){
            case -1:
                answer += "L";
                L = el;
                break;
            case 1:
                answer += "R";
                R = el;
                break;
            case 0:
                L_steps = Math.abs(grid[L][0] - grid[el][0]) + Math.abs(grid[L][1] - grid[el][1]);
                R_steps = Math.abs(grid[R][0] - grid[el][0]) + Math.abs(grid[R][1] - grid[el][1]);
                if(L_steps > R_steps){
                    answer += "R";
                    R = el;
                } else if (L_steps < R_steps){
                    answer += "L";
                    L = el;
                } else {
                    answer += hand;
                    eval(`${hand} = el`); //may affect performance?
                }
        }
    });
    return answer;
}

그리드로 접근 하신 분이 있는데 신선했다.

 

 

이걸 그리드로 표현한다면 숫자 5가 0,0으로 중심을 잡고

 

 [-1, 1]  [0, 1]  [1, 1]
 [-1, 0]  [0, 0]  [1, 0] 
 [-1,-1]  [0,-1]  [1,-1] 
 [-1,-2]  [0,-2]  [1,-2]

 

이런식으로 생각하면 된다. 

그래서 여기서 x 좌표를 보면 

왼쪽은 전부 -1 오른쪽은 전부 1이다. 

따라서 우리는 x좌표가 0인 것만 해결해주면 된다. 

그래서 코드를 보면 

 

switch (grid[el][0]){
            case -1:
                answer += "L";
                L = el;
                break;
            case 1:
                answer += "R";
                R = el;
                break;
            case 0:
                L_steps = Math.abs(grid[L][0] - grid[el][0]) + Math.abs(grid[L][1] - grid[el][1]);
                R_steps = Math.abs(grid[R][0] - grid[el][0]) + Math.abs(grid[R][1] - grid[el][1]);
                if(L_steps > R_steps){
                    answer += "R";
                    R = el;
                } else if (L_steps < R_steps){
                    answer += "L";
                    L = el;
                } else {
                    answer += hand;
                    eval(`${hand} = el`); //may affect performance?
                }
        }

 이렇게 x좌표에 따라 switch하게 되어있다. 

그리고 0일때는 점과 점사이 거리는 역시 맨하튼 거리로 했다.