키패드 누르기 (2020 카카오 인턴쉽)

해결 방법

특별한 알고리즘을 사용하지 않고 정직하게 푸는 문제였다. 우선 문제를 간단하게 정리해보겠다.

 

• 왼쪽 손가락은 '*' 위치에서, 오른쪽 손가락은 '#' 위치에서 시작한다.

• 키패드를 누르기 위해 손가락은 상하좌우로 1칸씩 움직이며 이동한다.

• 1, 4, 7 키패드는 왼쪽 손가락이 누른다.

• 3, 6, 9 키패드는 오른쪽 손가락이 누른다.

• 2, 5, 8, 0 키패드는 왼쪽과 오른쪽 손가락 중 가장 가까운 거리의 손가락이 누른다.

• 만약 왼쪽 오른쪽 손가락이 키패드와의 거리가 같다면 손잡이 위치에 따라 결정된다.

우선 손가락에서 키패드까지의 거리를 알기 위해서는 각 키패드의 위치를 지정해 주어야 한다. 위치는 pair<int, int>를 사용하여 각각 x축 y축으로 사용하였다.

 

위치를 지정해 주었다면 이제 거리를 구하는 함수가 필요하다. 손가락과 키패드 위치에서 x축과 y축의 차이를 합해주면 사이의 거리를 도출할 수 있다.

 

3, 6, 9와 1, 4, 7은 그냥 처리해주면 되고 2, 5, 8, 0이 되었을때 거리를 비교하여 처리해주면 된다.

 

만약 거리가 서로 같다면 같이 외부에서 입력받은 hand값을 비교해서 두 거리중 하나를 증가시켜 비교 할 수 있도록 한다.

 

left거리 = 4   right거리 = 4 로 같을 경우

* hand가 left라면 => right거리 + 1 => left거리가 더 가까우므로 left손가락을 사용하게 됨

* hand가 right라면 => left거리 + 1 => right거리가 더 가까우므로 right손가락을 사용하게 됨

 

구현 코드는 다음과 같다.

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

#define ASTERISK 10 // 별
#define SHARP 11 // 우물정자

// 절대값을 구해준다
int abs(int i) {
    return (i < 0) ? -i : i;
}

// 거리를 구해준다
int calcDist(pair<int, int> curPos, pair<int,int> numPos) {
    return abs(numPos.first - curPos.first) + abs(numPos.second - curPos.second);
}

string solution(vector<int> numbers, string hand) {
    string answer = "";
    
    vector<pair<int, int>> pos(12); // 위치값을 할당받고 설정해줌
    int idx = 0;
    pos[idx++] = make_pair(3, 1);
    for(int i = 0; i < 4; ++i) {
        for(int j = 0; j < 3; ++j) {
            if(i == 3 && j == 1) continue;
            pos[idx++] = make_pair(i, j);
        }
    }
    
    pair<int, int> hand_L = pos[ASTERISK]; 
    pair<int, int> hand_R = pos[SHARP];
    
    for(const auto num : numbers) {
        // 2, 5, 8, 0 -> left or right
        if(num == 0 || num % 3 == 2) {
            int leftDist = calcDist(hand_L, pos[num]);
            int rightDist = calcDist(hand_R, pos[num]);

            // 서로 같을 경우 손잡이 방향에 따라 결정해준다.
            if(leftDist == rightDist) 
                (hand == "left") ? ++rightDist : ++leftDist; 
            
            if(leftDist > rightDist) {
                answer += 'R';
                hand_R = pos[num];
            } else {
                answer += 'L';
                hand_L = pos[num];
            } 
        }   // 1, 4, 7 -> left 
        else if(num % 3 == 1) {
            answer += 'L';
            hand_L = pos[num];
        }   // 3, 6, 9 -> right 
        else {
            answer += 'R';
            hand_R = pos[num];
        }
    }
    
    return answer;
}