키패드 누르기 (feat. 프로그래머스, 67256번)

키패드 누르기
https://programmers.co.kr/learn/courses/30/lessons/67256

프로그래머스

반응형

// woohyeon.kim
#include <string>
#include <vector>
#include <algorithm>

using namespace std;

inline int calc(const int& number, const int& center)
{
    int ret_value = 4;
    if(center - number == 0)
        ret_value = 0;
    else if((abs(center - number) == 1) || (abs(center - number) == 3))
        ret_value = 1;
    else if((abs(center - number) == 2) || (abs(center - number) == 4) || (abs(center - number) == 6))
        ret_value = 2;
    else if((abs(center - number) == 5) || (abs(center - number) == 7) || (abs(center - number) == 9))
        ret_value = 3;
    return ret_value;
}

string solution(vector<int> numbers, string hand) {
    replace(numbers.begin(), numbers.end(), 0, 11);
    auto left_hand_position = 10, right_hand_position = 12;
    string answer = "";
    for(const auto& number : numbers)
    {
        if((number == 1) || (number == 4) || (number == 7))
        {
            answer.append("L");
            left_hand_position = number;
        }
        else if((number == 3) || (number == 6) || (number == 9))
        {
            answer.append("R");
            right_hand_position = number;
        }
        else
        {
            auto left = calc(left_hand_position, number);
            auto right = calc(right_hand_position, number);
            if(left < right)
            {
                answer.append("L");
                left_hand_position = number;
            }
            else if(left > right)
            {
                answer.append("R");
                right_hand_position = number;
            }
            else
            {
                if(hand.compare("right") == 0)
                {
                    answer.append("R");
                    right_hand_position = number;
                }
                else
                {
                    answer.append("L");
                    left_hand_position = number;
                }
            }
        }
    }
    return answer; 
}
// *&)*@*

단순하게 생각해보면

12칸으로 구분했을때, *은 10, 0은 11, #은 12로 치환할 수 있어요.

그럼 2,5,8,11 에서 현재 왼손의 번호 또는 오른손의 번호의 절대값 차이가 동일한 이동 위치입니다.

즉, 5에서 2로 가던 8로가던 |3|만큼의 이동은 1칸이 되고

5에서 1로가던 7로가던(왼손) 또는 5에서 3으로가던 9로가던(오른손) |2| 또는 |4|는 2칸을 이동하게 됩니다.

이런 형태로 트리를 짜두면 쉽게 구할 수 있어요.