[프로그래머스] 키패드 누르기

프로그래머스의

2020카카오인턴십

키패드 누르기를 풀어보았다.

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

 

원래는 시간 맞추고 다 풀고 싶었는데

3시간 동안 2개 풀었다ㅠㅠ

 

 

풀이법

1. 번호마다 각 위치를 저장한다.

2. 왼손과 오른손만을 쓰는 경우를 체크한다.

 3. 중앙의 숫자를 누르는 경우를 체크한다.

 - 왼손/오른손 중 누가 더 가까운가?

- 둘의 거리가 같다면 왼손/오른손 잡이 중 무엇인가? 

 

 

 

 

---

1. 번호마다 각 위치를 저장한다.

Pos구조체 배열을 만들어 키패드 번호와 좌표를 대치 해주었다.

0번을 누르면 Pos[0]로 접근하고 0의 좌표인 1,3을 반환해주었다.

struct Pos {
	// Pos 구조체와 내부 인자 선언
    int x, y; // 해당 번호의 좌표값 저장
};

구조체를 먼저 선언 했다.

 

 

 

 

    Pos p[10], handL = { 0, 3 }, handR = { 2, 3 };
    p[0].x = 1; p[0].y = 3;
    p[1].x = 0; p[1].y = 0;
    for (int i = 2; i < 10; i++) {
        p[i].x = (i-1) % 3;
        p[i].y = (i-1) / 3;
    }

p[] : 각 번호의 위치가 저장됨 

handL, handR : 현재 왼손과 오른손의 위치를 저장 

 

왼손 오른쪽 위치는 *, #에 각각 위치하도록 초기지정 했다.

0번과 1번을 제외하고 나머지 번호는 규칙에 맞게 반복문으로 값을 설정했다.

 

 

 

---

2. 왼손과 오른손만을 쓰는 경우를 체크한다.

// 입력된 숫자 백터 길이 파악
int len = numbers.size();
    // 길이 만큼 반복
    for (int i = 0; i < len; i++) {
    	현재 누를 번호의 위치 값 임시 저장  
        Pos temp = p[numbers[i]];

        // 왼손으로만 누르는 경우 : 1번, 4번, 7번을 누른 경우
        if (numbers[i] == 1 || numbers[i] == 4 || numbers[i] == 7) {
            handL = temp; // 왼손 위치 업데이트
            answer += "L"; // 답안 업데이트
        }
        // 오른손으로만 누르는 경우 : 3번, 6번, 9번을 누른 경우
        else if (numbers[i] == 3 || numbers[i] == 6 || numbers[i] == 9) {
            handR = temp; // 오른손 위치 업데이트
            answer += "R"; // 답안 업데이트
        }
        
        ...

왼손과 오른손으로 누르는 경우는 단순히 위치만 업데이트 하면 된다.

따라서 단순 if문에  handL/handR값과 답안을 업데이트해주면 된다.

 

 

 

 

---

3. 중앙의 숫자를 누르는 경우를 체크한다.

 

 

중앙의 숫자를 누르기 위해서는 다음 제약 조건을 맞추어야 한다.

1) 1칸 간격의 대각선은 못 간다.

2) 왼손, 오른손 중 가까운 손이 누른다.

3) 같은 거리인 경우 오른손잡이는 오른손, 왼손잡이는 왼손으로 누른다.

 

※ 위 이미지기준 왼손(파랑), 오른손(초록)이 해당 위치에 있고, 5를 눌러야 하면 왼손이 누른다.

대각 위치는 누를 수 없기 때문!!

 

 

 

 

 

제약조건의 파훼법은 간단했다.

바로 두 점 사이의 거리 공식을 이용하는 것!

 

 

 

각 케이스를 보며 설명하겠다.

 

①

왼손과 누를 번호의 거리 : 루트((1-1)^2 + (0-1)^2) = 1

오른손과 누를 번호의 거리 : 루트((2-1)^2 + (2-1)^2) = 1.4142135623..

왼손이 더 가깝다.

 

②

왼손과 누를 번호의 거리 : 루트((1-0)^2 + (0-1)^2) = 1.4142135623..

오른손과 누를 번호의 거리 : 루트((2-0)^2 + (2-1)^2) = 2.23606797..

왼손이 더 가깝다.

 

③

거리공식 쓰는 분들의 에러 케이스

왼손과 누를 번호의 거리 : 루트((2-0)^2 + (0-1)^2) = 2.23606797..

오른손과 누를 번호의 거리 : 루트((1-0)^2 + (3-1)^2) = 3

오른손이 더 가깝다? => 틀림

 

왼손은 7-2로 대각 이동이 아닌, 7-4-1-2로 이동하기 때문에 거리가 3이다!

따라서 ③번은 왼손 오른손이 거리가 같은 예이다.

 

이 오류를 극복하기 위해선 올림을 이용했다.

①의 왼손 1.4-> 2

②의 왼손/오른손 1.4->2, 2.2->3

③의 왼손/오른손 1.4->2, 2.2->3

위와 같이 올림을 이용하면 올바른 거리가 나온다.

 

 

 

double disL = ceil((sqrt(pow((handL.x - temp.x), 2) + pow((handL.y - temp.y), 2)) * 1000.0) / 1000.0);
double disR = ceil((sqrt(pow((handR.x - temp.x), 2) + pow((handR.y - temp.y), 2)) * 1000.0) / 1000.0);

왼손과 오른손의 거리를 구하는 코드

* 1000.0 / 1000.0를 한 이유

1.414213562... * 1000 = 1414.213562...

1414.213562... / 1000.0 = 1.414

예전에 반올림 오류 이후로 저걸 해야 맘이 편했다.

 

 

 

 

 		// 중앙 (2, 5, 8, 0)
        else {
            double disL = ceil((sqrt(pow((handL.x - temp.x), 2) + pow((handL.y - temp.y), 2)) * 1000.0) / 1000.0);
            double disR = ceil((sqrt(pow((handR.x - temp.x), 2) + pow((handR.y - temp.y), 2)) * 1000.0) / 1000.0);
            // 왼손이 더 가까운 경우
            if (disL < disR) {
                handL = temp;
                answer += "L";
            }
            // 오른손이 더 가까운 경우
            else if (disL > disR) {
                handR = temp;
                answer += "R";
            }
            // 거리가 같은 경우
            else {
                // 오른손잡이
                if (hand.compare("right") == 0) {
                    handR = temp;
                    answer += "R";
                }
                // 왼손잡이
                else {
                    handL = temp;
                    answer += "L";

                }
            }
        }

중앙숫자 판별 코드이다.

왼쪽, 오른쪽 중 가까운 쪽을 우선 체크 후,

거리가 같은 경우 왼손/오른손 잡이를 체크했다.

 

 

 

---

전체코드

#include <string>
#include <vector>
#include <math.h>

using namespace std;

struct Pos
{
    int x, y;
};

string solution(vector<int> numbers, string hand) {
    string answer = "";
    Pos p[10], handL = { 0, 3 }, handR = { 2, 3 };

    // 번호마다의 위치 부여
    p[0].x = 1; p[0].y = 3;
    p[1].x = 0; p[1].y = 0;
    for (int i = 2; i < 10; i++) {
        p[i].x = (i-1) % 3;
        p[i].y = (i-1) / 3;
    }

    int len = numbers.size();
    for (int i = 0; i < len; i++) {
        Pos temp = p[numbers[i]];

        // 좌
        if (numbers[i] == 1 || numbers[i] == 4 || numbers[i] == 7) {
            handL = temp;
            answer += "L";
        }
        // 우
        else if (numbers[i] == 3 || numbers[i] == 6 || numbers[i] == 9) {
            handR = temp;
            answer += "R";
        }
        // 중앙 (2, 5, 8, 0)
        else {
            double disL = ceil((sqrt(pow((handL.x - temp.x), 2) + pow((handL.y - temp.y), 2)) * 1000.0) / 1000.0);
            double disR = ceil((sqrt(pow((handR.x - temp.x), 2) + pow((handR.y - temp.y), 2)) * 1000.0) / 1000.0);
            // 왼손이 더 가까운 경우
            if (disL < disR) {
                handL = temp;
                answer += "L";
            }
            // 오른손이 더 가까운 경우
            else if (disL > disR) {
                handR = temp;
                answer += "R";
            }
            // 거리가 같은 경우
            else {
                // 오른손잡이
                if (hand.compare("right") == 0) {
                    handR = temp;
                    answer += "R";
                }
                // 왼손잡이
                else {
                    handL = temp;
                    answer += "L";

                }
            }
        }

    }

    return answer;
}