[프로그래머스 Level 1, C++] 키패드 누르기

문제 : 키패드 누르기

---

풀이 방법

키패드의 위치를 어떻게 구할까 생각하다가 그냥 각 키패드 번호의 좌표계를 만들어서 두 점사이의 거리 공식을 이용하면 풀 수 있겠다고 생각을 했었습니다.

 

왼쪽 열과 오른쪽 열은 무조건 누르는 손가락이 정해져있지만 가온데 열은 가까운 손가락으로 누르는 조건이 있습니다.

그렇다면 두 점사이의 거리 공식을 이용하면 구하겠지 했는데 막상 만들어 보니 실패라고 뜨더군요.

알고보니 유클리드 거리를 쓰는게 아니라 맨해튼 거리를 쓰는 것이 정답이었습니다.

 

 

우리가 알고 있는 두 점 사이의 공식이 유클리드 거리었고

 

 

이게 맨해튼 거리라고 합니다.

 

문제 조건에 상하좌우로 1칸씩 움직인다고 했기 때문에 맨해튼 거리 공식을 써서 풀어야 했던겁니다.

---

소스 코드

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

string solution(vector<int> numbers, string hand) {
    string answer = "";
    vector<vector<int>> hand_pos = {{0, 3},{2, 3}};
    vector<vector<int>> keypad_pos;
    // 1번부터 0,0 #을 2,3까지 해서 좌표로 넣음
    for(int i=0; i<4; i++) {
        for(int u=0; u<3; u++) {
            vector<int> temp;
            temp.push_back(u);
            temp.push_back(i);
            keypad_pos.push_back(temp);
        }
    }
    
    for(int & i : numbers) {
        if(i==1 || i==4 || i==7) {
            answer.push_back('L');
            hand_pos[0] = keypad_pos[i-1];
        }
        else if(i==3 || i==6 || i==9) {
            answer.push_back('R');
            hand_pos[1] = keypad_pos[i-1];
        }
        // 좌표 계산에 따른 결정
        else if(i==2 || i==5 || i==8 || i==0) {
            int index;
            if(i == 0 ) index = 11;
            else index = i;
            
            double temp[2];
            for(int u=0; u<2; u++) {
                temp[u] = abs(keypad_pos[index-1][0] - hand_pos[u][0]) +
                    abs(keypad_pos[index-1][1] - hand_pos[u][1]);
            }
            if(temp[0] < temp[1]) {
                answer.push_back('L');
                hand_pos[0] = keypad_pos[index-1];
            }
            else if(temp[0] == temp[1]) {
                if(hand == "left") {
                    answer.push_back('L');
                    hand_pos[0] = keypad_pos[index-1];
                }
                else {
                    answer.push_back('R');
                    hand_pos[1] = keypad_pos[index-1];
                }
            }
            else {
                answer.push_back('R');
                hand_pos[1] = keypad_pos[index-1];
            }
        }
    }
    return answer;
}