[Programmers 알고리즘, C++]#Level1_키패드 누르기

[Programmers 알고리즘, C++]#Level 1_키패드 누르기

 

Programmers 알고리즘 문제 풀이, Level1_키패드 누르기

STL 컨테이너 활용과 규칙을 찾아 풀이하는 문제입니다.

 

---

 

문제

 

 

풀이

 

먼저, "1 - 4 - 7"은 "L", 그리고 "3 - 6 - 9"는 "R"이 확정입니다.

 

따라서, C++가 제공하는 STL 컨테이너 중 "map"을 활용해봤습니다.

key 는 키패드의 숫자로 설정하고, 미리 확정된 손을 value로 하였습니다.

예를 들면, {1, "L"}, {3, "R"}, ... etc

물론, "2 - 5 - 8 - 0"은 정해진 손이 없기 때문에 "U(Undefined)"로 value를 저장합니다.

 

더불어, '*', '0', 그리고 '#'은 편의상 각각 10, 11, 그리고 12로 가정하고 진행했습니다.

 

우리가 주목할 점은 "2 - 5 - 8 - 0" 을 어느 쪽 손으로 누를 것인지 예측하는 것입니다.

문제에서 제공한 우선순위는 1) hand 2) 거리 순서입니다.

즉, 현재의 왼손 그리고 오른손 위치에서 "2 - 5 - 8 - 0" 중 한 개의 숫자까지의 거리를 먼저 계산하고,

거리가 같다면 "hand(주 손)"을 선택합니다. 이동 방향은 상, 하, 좌, 우만 가능하다고 제시하고 있습니다!

 

 

주어진 숫자까지의 거리를 계산하는 방법은 두 가지 경우를 갖습니다!

 

// 1 - 4 - 7 (왼손)과 3 - 6 - 9 (오른손)에서 2 - 5 - 8 - 0 중 한 개까지의 이동 거리
"( abs( 목표 숫자 - 현재 손의 위치 ) / 3 ) + ( abs( 목표 숫자 - 현재 손의 위치 ) % 3 )"

* abs() : 절대값으로 변환해주는 메서드

 

첫 번째 경우는 각각 "1 - 4 - 7"과 "3 - 6 - 9"에서 "2 - 5 - 8 - 0" 중 한 개의 키패드로 이동하는 경우로 위와 같습니다!

더 간단한 경우가 존재할것같지만, 최선입니다...

 

// 2 - 5 - 8 - 0 ( 오른손 or 왼손 )에서 다른 2 - 5 - 8 - 0 중 한 개까지의 이동 거리
"abs( 목표 숫자 - 현재 손의 위치 ) / 3"

 

두 번째 경우는 오른손 혹은 왼손이 "2 - 5 - 8 - 0" 중 한 개의 숫자에서 다른 숫자로 이동할 때의 거리입니다.

마찬가지로 위의 식과 같습니다! 

 

최종적으로, 거리 계산과 "hand(주손)"에 따라서 "2 - 5 - 8 - 0" 에 어느 쪽 손으로 누를지 결정합니다.

 

코드

#include <string>
#include <vector>
#include <map>
#include <utility>
#include <cmath>
#include <algorithm>

using namespace std;

map<int, char> m{
    {1, 'L'},
    {4, 'L'},
    {7, 'L'},
    {3, 'R'},
    {6, 'R'},
    {9, 'R'},
    // 2 - 5 - 8 - 0 은 정해진 손이 없어서, U로 합니다.
    {2, 'U'},
    {5, 'U'},
    {8, 'U'},
    {11, 'U'},
};

string solution(vector<int> numbers, string hand) {
    string answer = "";
    
    // 0 -> 11 로 교체
    replace_if(begin(numbers), end(numbers), [](int num){ return num == 0;}, 11);
    
    // "right" or "left" -> 'R' or 'L'
    if(hand == "left")
        hand = "L";
    else if (hand == "right")
        hand = "R";
    
    // * == 10 -> Left , # == 12 -> Right
    pair<int, int> currentHand(10, 12);
    
    int num = -1;
    for(int i=0; i < numbers.size(); i++)
    {
        num = numbers[i];
        
        // 항목 값이 'U'가 아니라면, 이미 확정된 손이 존재합니다!
        if( m[num] != 'U' )
        {
            answer.push_back(m[num]);
        }
        // 2 - 5 - 8 일 경우
        else
        {

            int leftDist = abs(num - currentHand.first);

            int rightDist = abs(num - currentHand.second);
            
            // 오른손 to 목표 숫자 , 왼손 to 목표 숫자 
            leftDist % 3 ? leftDist = (leftDist/3) + (leftDist%3) : leftDist /= 3;
            rightDist % 3 ? rightDist = (rightDist/3) + (rightDist%3) : rightDist /= 3;
            
            if( leftDist == rightDist)
            {
                answer.append(hand);
            }
            else{
                if ( min(leftDist, rightDist) == leftDist )
                    answer.push_back('L');

                else
                    answer.push_back('R');       
            }
        }
        if(answer.back() == 'L')
            currentHand.first = num;
        else
            currentHand.second = num;
    }
    return answer;
}