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

programmers.co.kr/learn/courses/30/lessons/67256

코딩테스트 연습 - 키패드 누르기

키패드 누르기 문제

구현 방법

이 문제를 처음 봤을 때, 특정 알고리즘/ 자료구조를 사용할 필요 없이 구현력을 요구하는 문제 같아 보였습니다.

 

이 문제를 해결할 로직은 다음과 같습니다

• 입력받은 숫자 배열을 처음부터 하나씩 탐색
• 숫자가 1, 4, 7 이면 왼손으로 누르고 왼손 위치를 해당 숫자로 이동.
• 숫자가 3, 6, 9 이면 오른손으로 누르고 오른손 위치를 해당 숫자로 이동.
• 숫자가 2, 5, 8, 0이면 해당 숫자와 왼손 위치의 거리, 오른손 위치의 거리를 구해 거리가 짧은 손으로 누르고, 거리가 같으면 입력받은 왼손잡이인지 오른손잡이인지 알려주는 변수로 파악해 해당 손으로 누르고 위치를 해당 숫자로 이동.

일단, 숫자 핸드폰의 키패드를 다음과 같이 x, y 좌표 쌍으로 이루어진 2차원 배열로 표현했습니다.

 

핸드폰의 키패드

1	2	3
4	5	6
7	8	9
*	0	#

x,y 좌표 쌍으로 표현  numPad

(0 , 0)	(0 , 1)	(0 , 2)
(1 , 0)	(1 , 1)	(1 , 2)
(2 , 0)	(2 , 1)	(2 , 2)
(3 , 0)	(3 , 1)	(3 , 2)

 

이렇게 표현을 하면 숫자와 좌표 쌍의 관계는 다음과 같습니다.

1번 숫자의 좌표 쌍은 (0,0) 즉 numPad의 0번째 요소

2번 숫자의 좌표쌍은 (0,1) 즉 numPad의 1번째 요소

...

n번 숫자의 좌표쌍은 (x, y) 즉 numPad의 n-1번째 요소

(단, 키패드의 숫자가 *이면 10으로 생각하고, 0번은 11로 생각하고 #은 12로 생각해야 합니다)

---

이렇게 좌표 쌍으로 키패드를 표현하면, 숫자들 간의 거리 구하기가 편해집니다.

좌표평면 위에서 거리를 구하듯이, 키패드의 숫자 2와 9의 거리를 구하려면 다음과 같은 수식으로 계산할 수 있습니다.

 

| (숫자2 좌표 쌍의 x 값 - 숫자 9 좌표 쌍의 x 값) | + | (숫자 2 좌표 쌍의 y 값 - 숫자 9 좌표 쌍의 y값) |

---

왼손, 오른손 위치 이동시키기

예를 들어 4번 버튼을 왼손으로 눌렀다고 하면, 왼손의 위치를 알려주는 leftPos 변수를 numPad[4-1] 로 옮겨주면 됩니다. 즉, 다음과 같이 손의 위치를 이동시킬 수 있습니다.

 

leftPos = numPad[numbers[i] - 1]

 

 

위 로직을 아래 소스코드와 같이 구현했습니다.

 

소스코드

 

#include <bits/stdc++.h>
using namespace std;

string solution(vector<int> numbers, string hand) {
    string answer = "";
    
    //왼손 위치, 오른손 위치 (x,y)좌표로
    pair<int,int> leftPos, rightPos;

    //숫자 판 정의 1번은 (0,0), 2번은 (0,1) ... 등등
    //숫자 판의 1은, numPad의 0 번째, 숫자 판의 2는, numPad의 1번째 임을 꼭 확인!
    pair<int,int> numPad[13] = {
            {0,0},{0,1}, {0,2},
            {1,0},{1,1}, {1,2},
            {2,0},{2,1}, {2,2},
            {3,0},{3,1}, {3,2}
    };

    //왼손, 오른손 초기 위치 설정
    leftPos = {3,0}; // *
    rightPos = {3,2}; // #


    //입력 받은 숫자 하나씩 검토
    for(int i=0;i<numbers.size();i++) {
        //1, 4, 7 이면 왼손으로 누르고 왼손 포지션 변경
        if(numbers[i] == 1 || numbers[i] == 4 || numbers[i] == 7) {
            answer += "L";
            leftPos = numPad[numbers[i]-1];
        } //3, 6, 9 이면 오른손으로 누르고 오른손 포지션 변경
        else if(numbers[i] == 3 || numbers[i] == 6 || numbers[i] == 9) {
            answer += "R";
            rightPos = numPad[numbers[i]-1];
        }
        else if(numbers[i] == 2 || numbers[i] == 5 || numbers[i] == 8 || numbers[i] == 0) {
            //0 번은 예외적으로 11로
            if(numbers[i] == 0) {
                numbers[i] = 11;
            }
            //거리 계산시 x좌표의 차이의 절대값 + y좌표의 차이의 절대값
            int leftDistance =abs(numPad[numbers[i]-1].first - leftPos.first) + abs(numPad[numbers[i]-1].second - leftPos.second);
            int rightDistance = abs(numPad[numbers[i]-1].first - rightPos.first) + abs(numPad[numbers[i]-1].second - rightPos.second);

            //왼손이 가까우면
            if(leftDistance < rightDistance) {
                answer += "L";
                leftPos = numPad[numbers[i]-1];
            }//오른손이 가까우면
            else if(leftDistance > rightDistance) {
                answer += "R";
                rightPos = numPad[numbers[i]-1];
            }//거리가 같으면 왼손 잡이인지, 오른손 잡이인지 판별
            else {
                if(hand =="right") {
                    answer += "R";
                    rightPos = numPad[numbers[i]-1];
                } else {
                    answer += "L";
                    leftPos = numPad[numbers[i]-1];
                }
            }
        }
    }

    return answer;
}