[프로그래머스/JavaScript] Lv.3 숫자 타자 대회

 

 

해당 문제는 시간 복잡도를 개선하여 효율성을 높이는 문제이다.

 

 

 

 

 

프로그래머스

 

 

 

 

---

1. 문제 설명

키패드

위와 같은 모양으로 배열된 숫자 자판이 있습니다. 숫자 타자 대회는 이 동일한 자판을 사용하여 숫자로만 이루어진 긴 문자열을 누가 가장 빠르게 타이핑하는지 겨루는 대회입니다.

대회에 참가하려는 민희는 두 엄지 손가락을 이용하여 타이핑을 합니다. 민희는 항상 왼손 엄지를 4 위에, 오른손 엄지를 6 위에 두고 타이핑을 시작합니다. 엄지 손가락을 움직여 다음 숫자를 누르는 데에는 일정 시간이 듭니다. 민희는 어떤 두 숫자를 연속으로 입력하는 시간 비용을 몇몇 가중치로 분류하였습니다.

• 이동하지 않고 제자리에서 다시 누르는 것은 가중치가 1입니다.
• 상하좌우로 인접한 숫자로 이동하여 누르는 것은 가중치가 2입니다.
• 대각선으로 인접한 숫자로 이동하여 누르는 것은 가중치가 3입니다.
• 같지 않고 인접하지 않은 숫자를 누를 때는 위 규칙에 따라 가중치 합이 최소가 되는 경로를 따릅니다.

예를 들어 1 위에 있던 손가락을 0으로 이동하여 누르는 것은 2 + 2 + 3 = 7 만큼의 가중치를 갖습니다.
단, 숫자 자판은 버튼의 크기가 작기 때문에 같은 숫자 버튼 위에 동시에 두 엄지 손가락을 올려놓을 수 없습니다. 즉, 어떤 숫자를 눌러야 할 차례에 그 숫자 위에 올려져 있는 손가락이 있다면 반드시 그 손가락으로 눌러야 합니다.

숫자로 이루어진 문자열 numbers가 주어졌을 때 최소한의 시간으로 타이핑을 하는 경우의 가중치 합을 return 하도록 solution 함수를 완성해주세요.

제한 사항

 

 

---

2. 입출력 예

입출력 예

 

 

 

 

---

3. 문제 풀이

가짓수만큼 만들어 최소 값을 구하게 되면, 16~20 테스트를 통과할 수 없다. 중복을 제거하는 것으로 시간 복잡도를 개선해서 로직을 수정해야 한다.

중복 제거

• Left, Right와 Left, Right의 동일한 가중치를 갖는다. ( ex 4,6 = 6,4 )
• 같은 레벨의 Left, Right와 Left, Right는 같은 패턴을 반복한다. ( ex 보라색, 노란색, 초록색 삼각형 동일한 패턴으로 하위 레벨 생성) 

 

function solution(numbers) {
    // 1) 0~9 까지의 가중치 2차원 배열로 생성한다.
    dist = distance();
    
    // 6) 최초 위치 left, right를 key 값으로 가중치 넣는다.
    const map = new Map([['46', 0]]);

    // 7) 문자열 만큼 반복한다.
    for(let i=0; i<numbers.length; i++){
        // 8) 이동 가능 가짓수 담은 map을 복사한다.
        let tmp = new Map(map);
        let num = numbers[i];  
        
        // 9) map을 초기화하고 다시 이동 가능 가짓수를 담는다.
        map.clear();
        // 10) 현재 이동 가능한 가짓수(tmp) 만큼 반복
        for (let [key, val] of tmp) {
            // 11) key값을 left, right로 자른다.
            let [left, right] = key.split('');
            
            // 12) 오른쪽 이동 중복을 제거 
            if(map.has(left+num) || map.has(num+left)) {
                let rightKey = map.has(left+num) ? left+num : num+left;
                
                // 13) 중복일 경우 가중치 최소 값을 담는다
                map.set(rightKey, Math.min(map.get(rightKey), val + dist[right][num]));
            } else {
                // 14) 왼쪽 이동
                if(left != num) map.set(left+''+num, val+dist[right][num]);
            }
            // 15) 왼쪽 이동 중복 제거
            if(map.has(num+right) || map.has(right+num)) {
                let leftKey = map.has(num+right) ? num+right : right+num;
                map.set(leftKey, Math.min(leftKey, val + dist[left][num]));
            } else {
                // 16) 오른쪽 이동
                if(right != num) map.set(num+''+right, val+dist[left][num]);   
            }
        }
    }
    // 17) 마지막 이동 가능한 가짓수 중 최소 값 return
    return [...map.entries()].reduce((pv, cv) => pv[1] < cv[1] ? pv : cv)[1];
}


// 2) 가중치 구하는 함수  
function distance() {
	// 3) 0~9까지 2차원 배열을 0 값으로 생성한다.
    const w = Array.from({length: 10}, () => Array(10).fill(0));
    
    // 4) 가중치 값을 구해 하나씩 넣는다.
    for (let i = 0; i < 10; i++) {
        for (let j = 0; j<10; j++) {
            /*  
                1. position(i)로 현재 클릭된 값(i)의 위치(x,y)를 찾는다. 
                - x = pad의 행 이동거리(i의 행 - j의 행)
                - y = pad의 열 이동거리(i의 열 - j의 열)
                
                2. 가중치 계산 
                - i, j가 같으면 움직이지 않는 것으로 가중치 1
                - 대가선 이동 : min(x, y의 최소 값) * 3
                - 직선 이동 : 절대값(max - min) * 2
            */
            let x = Math.abs(position(i)[0] - position(j)[0]);
            let y = Math.abs(position(i)[1] - position(j)[1]);
            let min = Math.min(x, y);
            let max = Math.max(x, y)
            w[j][i] = i===j ? 1 : min*3 + Math.abs(max-min)*2; 
        }
    }
    return w
}
// 5) i or j의 현재 위치 반환
function position(num){
    const pad = [
                ["1", "2", "3"],
                ["4", "5", "6"],
                ["7", "8", "9"],
                ["*", "0", "#"]
            ];
    let p = []
    pad.find((arr, i) => {
        if(arr.includes(num+'')) {
             p = [i, arr.indexOf(num+'')];
        }
    });
    return p;
}