C++:: 프로그래머스 < 숫자 타자 대회 >

푸는데 상당히 오래걸린 문제이다. 풀이의 핵심은 먼저 숫자에서 타켓 숫자 까지의 가중치값을 구하고, unordered_map에 최종 자판과 가중치값을 넣어서 준다. 이를 통해 중복되는 경로 에대해서 최소값에 대한 계산을 하기떄문에 계산이 적어지게된다.

#include <string>
#include <vector>
#include <unordered_map>
using namespace std;

int get_xcord(int num) {// 자판의 x좌표
    if (num == 0) return (1);
    return ((num - 1) % 3);
}

int get_ycord(int num) {/ 자판의 y좌표
    if (num == 0) return (3);
    return ((num - 1) / 3);
}

int get_move_cnt(int start, int target) {// start 부터 target까지의 가중치 계산
    int res = 0;
    int dist_x = abs(get_xcord(start) - get_xcord(target)); 
    int dist_y = abs(get_ycord(start) - get_ycord(target));

    if (dist_x == 0 && dist_y == 0) return (1);// 바로 해당 자판이면
    while (dist_x || dist_y) {
        if (dist_x && dist_y) {// 대각이면
            res += 3;
            dist_x--;
            dist_y--;
        } else if (dist_x) {
            res += 2;
            dist_x--;
        } else {
            res += 2;
            dist_y--;
        }
    }
    return (res);
}

string get_go_to(char a, char b) {// 손가락 위치를 오름차순으로 리턴
    string res = "";

    if (a > b) {
        res += b;
        res += a;
    } else {
        res += a;
        res += b;
    }
    return (res);
}


int solution(string numbers) {
    int answer = 0;
    vector<pair<string, int>> positions = {{"46", 0}};// 맨처음 위치
    for (auto num : numbers) {
        unordered_map<string, int> um;// 현재 자판에서 갈수있는 경우들을 넣어준다.
        for (auto pos : positions) {
            if ((pos.first[0] == num || pos.first[1] == num)) {
            	// 타겟 번호위에 이미 있으면
                if (um[pos.first] == 0) um[pos.first] = pos.second + 1;
                else um[pos.first] = min(um[pos.first], pos.second + 1);
                continue ;
            }
            string go_to_left, go_to_right;
            // 왼쪽번호에서 타겟번호로 간다면
            int left_cnt = pos.second + get_move_cnt(pos.first[1] - '0' , num - '0');
            go_to_left = get_go_to(pos.first[0], num);
            if (um[go_to_left] == 0 || um[go_to_left] > left_cnt) um[go_to_left] = left_cnt;
            // 오른쪽번호에서 타겟번호로 간다면
            int right_cnt = pos.second + get_move_cnt(pos.first[0] - '0' , num - '0');
            go_to_right = get_go_to(pos.first[1], num);
            if (um[go_to_right] == 0 || um[go_to_right] > right_cnt) um[go_to_right] = right_cnt;
        }
        positions.clear();// 이전 자판위치를 삭제 후
        for (auto m : um) positions.push_back({m.first, m.second});// 새로 넣어준다.
    }
    answer = positions[0].second;
    for (auto position : positions) answer = min(answer, position.second);// 가장 작은값이 답
    return answer;
}