Lv1_[키패드 누르기, C++] 알고리즘 정리 - 프로그래머스

프로그래머스

문제 내용, 조건, 예시는 프로그래머스 사이트 참조

---

순대대로 누르는 번호가 어디에 위치한지 파악이 우선이기 때문에 아래와 같이 키패드를 구분해서 저장했다.

• vector<int> left_keypad      = { 1, 4, 7, 10 };
• vector<int> center_keypad = { 2, 5, 8, 0 };
• vector<int> right_keypad    = { 3, 6, 9, 11 };

 

구분하기 위해 들어온 번호에 3을 나머지연산(mod[%])하게 되면 원하는 키패드 위치가 나온다.

ex)

• 5가 들어오면 (5%3 = 2) 나머지가 2이므로 CENTER(2)
• 10이 들어오면 (10%3 = 1) 나머지가 1이므로 LEFT(1)
• 9가 들어오면 (9%3 = 0) 이지만 위의 두개가 일치하지 않으면 else로 빠지게 둠. RIGHT(3)

가독성을 위해 enum 정의
enum {

  LEFT = 1,
  CENTER = 2,
  RIGHT = 3
};

예외)

• 0일 때는 CENTER(2)가 될 수 있도록 조건값 넣음
• *(10), #(11)은 들어오지 않기 때문에 번호가 위의 조건에 일치하지 않게 해도 상관 없음

if ((keyNum == 0) || (keyNum % 3 == CENTER)) {
	// 양손 거리 구한 후 비교후 작은 값의 손으로 처리
} else if (keyNum % 3 == LEFT) {
	// 왼손으로 처리 "L"
} else { // (keyNum % 3 == 0) RIGHT
	// 오른손으로 처리 "R"
}

거리 구한 방법은

• 좌우거리(LEFT, CENTER, RIGHT)거리 측정 (0 또는 1)
• 상하거리 keyNum간의 index 차이

 ex) 1, 8의 거리는 2 {1은 index[0], 8은 index[2]이므로 abs(0-2)=2}

 

위와 같은 사항을 고려해서 풀어줬다.

 

#include <string>
#include <vector>
 
using namespace std;
 
enum {
    LEFT = 1,
    CENTER = 2,
    RIGHT = 3
};
 
vector<int> left_keypad = { 1, 4, 7, 10 };
vector<int> center_keypad = { 2, 5, 8, 0 };
vector<int> right_keypad = { 3, 6, 9, 11 };
vector<vector<int>> total_keypad = { left_keypad, center_keypad, right_keypad };
 
int getIndex(int keypad_index, int keyNum) {
    int vec_index = 0;
    vector<int> keypad = total_keypad[keypad_index - 1];
    for(auto index : keypad) {
        if(keyNum == index) {
            break;
        } else {
            vec_index++;
        }
    }
    return vec_index;
}
 
 
string solution(vector<int> numbers, string hand) {
    string answer = "";
 
    string LeftHandStr = "L";
    string RightHandStr = "R";
    int Myhand_index;
 
    // 손 잡이 파악
    if (hand.compare("left") == 0) {
        Myhand_index = LEFT;
    } else {
        Myhand_index = RIGHT;
    }
 
    int leftHand_num = 10;  // *
    int leftHand_Index = LEFT;
 
    int rightHand_num = 11;  // #
    int rightHand_Index = RIGHT;
 
    // pos : 벡터 index위치,
    // num : 키페드 숫자
    // index : LEFT, CENTER, RIGHT
    for (auto keyNum : numbers)
    {
        // 누른 키가 어디 있는지 판단
        int PressHandIndex = 0;
        if ((keyNum == 0) || (keyNum % 3 == CENTER)) {
            // center
            PressHandIndex = CENTER;
            int Press_pos = getIndex(PressHandIndex, keyNum);
 
            // 양손 비교 후 이동
            int LeftHand_pos = getIndex(leftHand_Index, leftHand_num);
            int RightHand_pos = getIndex(rightHand_Index, rightHand_num);
 
            // 거리 계산
            int left_distance = abs(PressHandIndex - leftHand_Index) + abs(Press_pos - LeftHand_pos);
            int right_distance = abs(rightHand_Index - PressHandIndex) + abs(Press_pos - RightHand_pos);
 
            if (left_distance == right_distance) {
                if (Myhand_index == LEFT) {
                    leftHand_num = keyNum;
                    leftHand_Index = PressHandIndex;
 
                    answer += LeftHandStr;
                } else {
                    rightHand_num = keyNum;
                    rightHand_Index = PressHandIndex;
 
                    answer += RightHandStr;
                }
            } else if (left_distance > right_distance) {
                rightHand_num = keyNum;
                rightHand_Index = PressHandIndex;
 
                answer += RightHandStr;
            } else {
                leftHand_num = keyNum;
                leftHand_Index = PressHandIndex;
 
                answer += LeftHandStr;
            }
        } else if (keyNum % 3 == LEFT) {
            // left
            PressHandIndex = LEFT;
 
            // 왼쪽손만 이동
            leftHand_num = keyNum;
            leftHand_Index = PressHandIndex;
 
            answer += LeftHandStr;
        } else { // (keyNum % 3 == 0)
            // right
            PressHandIndex = RIGHT;
 
            // 오른쪽 손만 이동
            rightHand_num = keyNum;
            rightHand_Index = PressHandIndex;
 
            answer += RightHandStr;
        }
    }
 
    return answer;
}

 

비교용 결과

 

↓↓↓↓↓↓ 유익했다면 하트 뿅 ♥ ↓↓↓↓↓↓