프로그래머스 [2020 카카오 인턴십 / 키패드 누르기](C++) -yes6686- 티스토리

프로그래머스 문제 풀이: 키패드 누르기

---

문제 링크: 문제 보기

문제 설명:

스마트폰 키패드에서 왼손과 오른손을 사용하여 번호를 입력할 때, 특정 규칙에 따라 어떤 손을 사용할지를 결정하는 문제입니다. 1, 4, 7은 왼손, 3, 6, 9는 오른손, 나머지 숫자는 현재 손의 위치와 hand 설정값에 따라 선택됩니다.

---

문제 해결 코드

#include <iostream>
#include <string>
#include <vector>
#include <map>
#include <cmath>

using namespace std;

// 키패드 좌표 저장
map<char, pair<int, int>> keyMap;

string solution(vector<int> numbers, string hand) {
    string answer = "";

    // 키패드 위치 매핑
    string layout = "123456789*0#";
    int index = 0;
    for (int i = 0; i < 4; i++) {
        for (int j = 0; j < 3; j++) {
            keyMap[layout[index++]] = {i, j};
        }
    }

    // 왼손과 오른손의 초기 위치
    char leftPos = '*', rightPos = '#';

    for (int num : numbers) {
        char key = num + '0';

        // 왼쪽 열 숫자(1, 4, 7)
        if (key == '1' || key == '4' || key == '7') {
            leftPos = key;
            answer += "L";
        }
        // 오른쪽 열 숫자(3, 6, 9)
        else if (key == '3' || key == '6' || key == '9') {
            rightPos = key;
            answer += "R";
        }
        // 가운데 열 숫자(2, 5, 8, 0)
        else {
            pair<int, int> target = keyMap[key];
            pair<int, int> leftDist = keyMap[leftPos];
            pair<int, int> rightDist = keyMap[rightPos];

            // 맨해튼 거리 계산
            int leftSteps = abs(leftDist.first - target.first) + abs(leftDist.second - target.second);
            int rightSteps = abs(rightDist.first - target.first) + abs(rightDist.second - target.second);

            if (leftSteps < rightSteps) {
                leftPos = key;
                answer += "L";
            } else if (leftSteps > rightSteps) {
                rightPos = key;
                answer += "R";
            } else {
                if (hand == "right") {
                    rightPos = key;
                    answer += "R";
                } else {
                    leftPos = key;
                    answer += "L";
                }
            }
        }
    }

    return answer;
}

---

코드 설명

• 핵심 알고리즘: 각 숫자의 위치를 저장한 후, 현재 손의 위치와 비교하여 맨해튼 거리를 계산해 최적의 손을 결정합니다.
• 구현 세부사항:
• 키패드의 각 숫자 위치를 map에 저장합니다.
• 1, 4, 7은 왼손이, 3, 6, 9는 오른손이 입력합니다.
• 2, 5, 8, 0은 현재 손의 위치와 거리 비교 후, 가까운 손을 사용합니다.
• 거리가 같다면 hand 설정값을 사용해 손을 결정합니다.
• 시간 복잡도 분석:
• 키패드 매핑: O(1)
• 입력 숫자 순회: O(n), 여기서 n은 numbers의 크기
• 총 시간 복잡도: O(n)

---

결과

이 코드는 입력된 숫자 목록에 따라 최적의 손을 선택하여 문자열을 반환합니다. 맵을 활용해 키패드 좌표를 저장하여 효율적으로 거리 계산을 수행합니다.

다른 접근 방식으로는 배열을 이용해 좌표를 미리 저장하는 방법이 있으며, 이는 unordered_map을 활용할 경우 탐색 성능이 더 향상될 수 있습니다.