숫자 타자 대회

사이트: Programmers
난이도: lv3

문제

핸드폰 숫자판 배열과 임의의 문자열이 주어졌을 때, 가장 적은 비용으로 해당 문자열을 입력하는 비용을 출력하라.

1. 나의 풀이

greedy 알고리즘으로 풀려고 했는데, 아무래도 그렇게 하면 안되겠다는 생각이 들었다. 최적화된 이동 경로로 풀어야 되는데, greedy를 사용할 경우 최적화 되지 않는 경로가 존재해서 테스트케이스 통과를 하지 못했다.

예를 들어, 51238이라는 입력값이 들어오면 내가 짠 코드는 다음과 같이 실행된다.

left = 4, right = 6, target = 5
4 -> 5 = 2
6 -> 5 = 2
total = 2

// left < right가 아니므로
left = 4, right = 5, target = 1
4 -> 1 = 2
5 -> 1 = 3
total = 4

// left < right 이므로
left = 1, right = 5, target = 2
1 -> 2 = 2
5 -> 2 = 2
total = 6

// left < right가 아니므로
left = 1, right = 2, target = 3
1 -> 3 = 4
2 -> 3 = 2
total = 8

// left < right가 아니므로
left = 1, right = 3, target = 8
1 -> 8 = 5
3 -> 8 = 5
total = 13

올바른 경로 대로라면 아래와 같아야 된다.

1. left = 4, right = 6, target = 5
2. left = 4, right = 5, target = 1
3. left = 1, right = 5, target = 2
4. left = 2, right = 5, target = 3
5. left = 3, right = 5, target = 8
6. left = 3, right = 8

total = 10

우선은 시간을 더 지체할 수 없어서, 다른 사람의 풀이를 찾아보았다.

function createGraph() {
    const n = [
        [1, 2, 2], [1, 4, 2], [1, 5, 3],
        [2, 3, 2], [2, 5, 2], [2, 6, 3], [2, 4, 3],
        [3, 5, 3], [3, 6, 2],
        [4, 5, 2], [4, 7, 2], [4, 8, 3],
        [5, 7, 3], [5, 8, 2], [5, 6, 2], [5, 9, 3],
        [6, 8, 3], [6, 9, 2],
        [7, 8, 2], [7, 10, 2], [7, 11, 3],
        [8, 9, 2], [8, 10, 3], [8, 11, 2], [8, 12, 3],
        [9, 11, 3], [9, 12, 2]
    ];
    const graph = Array.from(
        new Array(13), 
        () => new Array(13)
    );

    for (const [u, v, w] of n) {
        graph[u][v] = w;
        graph[v][u] = w;
    }
    
    return graph;
}

function bfs(start, end, graph) {
    const queue = [[start, 0]];
    const visited = [];
    visited[start] = true;

    let result = Infinity;
    while(queue.length) {
        const [current, total] = queue.shift();
        
        for (let i = 1; i < graph[current].length; i++) {
            const weight = graph[current][i];

            if (
                weight > 0 &&
                !visited[i]
            ) {
                if (i == end) {
                    result = Math.min(result, total + weight);
                } else {
                    queue.push([i, total + weight]);
                    visited[i] = true;
                }
            }
        }
    }
    
    return result;
}

function solution(numbers) {
    const graph = createGraph();
    const hands = [4, 6];
    const dp = Array.from(
        new Array(13), 
        () => new Array(13)
    );

    const convertNumber = (numStr) => {
        switch(numStr) {
            case "*":
                return 10;
            case "0":
                return 11;
            case "#":
                return 12;
            default:
                return +numStr;
        }
    }
    
    let total = 0;
    for (let i = 0; i < numbers.length; i++) {
        const num = convertNumber(numbers[i]);
        const [left, right] = hands.map(hand => {
            let weight;

            if (hand === num) {
                weight =  1;
            } else if (dp[hand][num] > 0) {
                weight = dp[hand][num];
            } else {
                weight = bfs(hand, num, graph);
                dp[hand][num] = weight;
            }

            return weight;
        });
        
        if (left < right) {
            total += left;
            hands[0] = num;
            
        } else {
            total += right;
            hands[1] = num;
        }
    }
    
    return total;
}

2. 다른사람의 풀이

해당 문제 풀이를 올려놓은 블로그가 있어서 첨부했다.

[코딩테스트] 프로그래머스 숫자 타자 대회 (JavaScript)