2020 카카오 인턴쉽 [키패드 누르기] Lv.1

문제 설명

스마트폰 전화 키패드의 각 칸에 다음과 같이 숫자들이 적혀 있습니다.

 전화 키패드에서 왼손과 오른손의 엄지손가락만을 이용해서 숫자만을 입력하려고 합니다.
맨 처음 왼손 엄지손가락은 * 키패드에 오른손 엄지손가락은 # 키패드 위치에서 시작하며, 엄지손가락을 사용하는 규칙은 다음과 같습니다.

1. 엄지손가락은 상하좌우 4가지 방향으로만 이동할 수 있으며 키패드 이동 한 칸은 거리로 1에 해당합니다.
2. 왼쪽 열의 3개의 숫자 1, 4, 7을 입력할 때는 왼손 엄지손가락을 사용합니다.
3. 오른쪽 열의 3개의 숫자 3, 6, 9를 입력할 때는 오른손 엄지손가락을 사용합니다.
4. 가운데 열의 4개의 숫자 2, 5, 8, 0을 입력할 때는 두 엄지손가락의 현재 키패드의 위치에서 더 가까운 엄지손가락을 사용합니다.
   4-1. 만약 두 엄지손가락의 거리가 같다면, 오른손잡이는 오른손 엄지손가락, 왼손잡이는 왼손 엄지손가락을 사용합니다.

순서대로 누를 번호가 담긴 배열 numbers, 왼손잡이인지 오른손잡이인 지를 나타내는 문자열 hand가 매개변수로 주어질 때, 각 번호를 누른 엄지손가락이 왼손인 지 오른손인 지를 나타내는 연속된 문자열 형태로 return 하도록 solution 함수를 완성해주세요.

 

나의 풀이

문제를 풀기 위해 접근 방법을 먼저 생각해보겠습니다. 

1. [1, 4, 7]은 왼손으로만 누를 수 있습니다.

2. [3, 6, 9]는 오른손으로만 누를 수 있습니다. 

3. [2, 5, 8, 0]은 왼손과 오른손 중 거리가 가까운 손가락으로 누를 수 있습니다.

3-1. 만약 다음으로 눌러야 하는 숫자가 왼손, 오른손으로부터 같은 거리에 있다면 hand에 저장된 문자열을 통해서 어떤 손으로 누를 것인지를 결정합니다.

 

switch-case문으로도 충분히 풀이할 수 있겠지만, 필자는 if문의 중첩으로 풀이하였습니다. 

이 문제에서 핵심은 거리 개념입니다. 1과 2는 어차피 특정 손으로만 누를 수 있기 때문에 고려할 사항이 아니지만, 3을 누를 수 있는 손은 두 가지 이므로, 이 경우에 대해서 조건을 나누어서 생각해볼 필요가 있습니다. 

 

지문에서 보면 거리 개념은 현재 위치로부터 상하좌우로 한 칸당 1로 계산한다고 했습니다. 

그렇다면 거리를 구하기 위해서는 무엇이 필요할까요? 

맞습니다. 현재 위치를 알 수 있도록 키패드를 좌표화하여 왼손의 위치, 오른손의 위치 그리고 다음에 눌러야 할 번호의 위치를 저장해야 합니다.

먼저 키패드의 좌표화를 진행하겠습니다. 

위의 사진을 참고해서 봐주시면 됩니다. 

1    2    3

4    5    6

7    8    9

10  11   12

 

1~9에 해당하는 숫자는 달라진 것이 없지만, * -> 10, 0 -> 11, # -> 12로 매핑해주었습니다. 

왼손과 오른손의 시작 위치를 지문에서 지정해주었기 때문에 변수를 만들어서 초기화해줍니다. 

LHandPos -> 왼손의 현재 위치

RhandPos -> 오른손의 현재 위치

 

반복 횟수는 눌러야 할 숫자의 개수만큼 반복을 진행하고 

조건은 크게 다음과 같이 지정해주었습니다. 

if(왼손으로만 누를 수 있는 경우) {

    "1"

} else if (오른손으로만 누를 수 있는 경우){

    "2"

} else { //왼손과 오른손 모두 누를 수 있는 경우

    

    if(왼손이 더 먼 경우){

        "3"

    } else if (오른손이 더 먼 경우) {

        "4"

    } else {//거리가 같은 경우 

        "5"

    }

}

1과 2번 영역은 직관적으로 이해할 수 있는 코드이기 때문에 3,4,5번 영역만 설명하도록 하겠습니다.

 

3, 4, 5번 영역을 설명하기 전에 거리를 계산하는 메서드를 먼저 설명하겠습니다. 

거리를 계산하기 위해서는 "현재 위치"와 "다음으로 눌러야 하는 숫자"를 매개변수로 받았습니다. 

숫자만을 누른다고 했기 때문에 #과 *은 누를 일이 없어서 처음에 초기화만 해주었지만,

0은 누를 일이 있기 때문에 혹여나 현재 위치가 0이거나 다음에 눌러야 하는 값이 0으로 매개변수를 통해 전달된다면 

반드시 값을 위에서 지정한 좌표값으로 바꾸어 주어야 합니다. 0(x), 11(o) 

 

좌표값을 계산하는 방법만 이해하면 이 문제는 80% 해결했다고 보셔도 무방합니다. 

다음과 같은 키패드 좌표를 그대로 사용하여 연산을 적용하면 두 값에 대해 상대적인 위치 값을 구할 수가 없습니다. 

1    2    3

4    5    6

7    8    9

10  11   12

예를 들어, 왼손이 4에 오른손이 6 이런 식으로 같은 선상에 있다면 거리는 6-4 = 2로 편하게 구할 수 있지만, 

왼손이 1, 오른손이 5에 있으면 거리는 하 -> 우 or 우 -> 하 이런식으로 2가 됩니다만 두 숫자 1과 5를 두고 일반화된 식을 도출할 수 없습니다. 

 

일반화된 식을 도출하기 위해서 사용할 방법은 키패드에 2차원 배열의 개념을 도입하여, 두 값이 표준화된 좌표계 위에 있을 수 있도록 해주겠습니다. 그러기 위해 모든 값에서 1을 빼주고, 행의 인덱스는 3을 나누어 몫을 취하고, 열 인덱스는 3으로 나눈 나머지를 취합니다.

그렇게 한다면, 두 지점의 x좌표 값의 차이 + y좌표 값의 차이의 결괏값을 통해서 대각선이 아닌 상하좌우로만 이뤄진 거리를 구할 수 있습니다. 

위의 좌표를 x, y(기존 값) 형태로 표현하면 다음과 같습니다. 

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

1,0(4)      1,1(5)      1,2(6)

2,0(7)      2,1(8)      2,2(9)

3,0(10)    3,1(11)     3,2(12)

 

이런 식으로 좌표를 표준화시켜주면 위에서는 구할 수 없었던 일반화된 식으로 거리를 계산할 수 있습니다.

1과 5 사이의 거리를 구하기 위해선 |1.x - 5.x| + |1.y + 5.y|의 연산을 수행하면 됩니다. 우리가 알고 싶은 것은 두 지점 사이의 거리이지 크기 비교가 아니기 때문에, 절댓값을 취해줍니다. 

결과는 |0-1| + |0-1| = 2로 정확한 결과가 나왔습니다.

이를 코드로 구현한 것이 바로 위의 이미지입니다.

 

혹여나 location-1, value-1을 보고 왜 1을 제거하는지에 대해 궁금한 사람이 있을지 몰라 간략히 설명하겠습니다. 

위의 예시와 다르게 -1을 하지 않고서 나누기 3 연산을 하면 다음과 같습니다.

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

1,1(4)      1,2(5)      2,0(6)

2,1(7)      2,2(8)      3,0(9)

3,1(10)    3,2(11)     4,0(12)

 

척 봐도 알아보기 힘들 정도로 좌표값이 복잡하게 생겨있습니다. 사실 -1을 하던 안 하던 계산 값은 똑같이 나오지만, 이 문제에서 더 확장된 문제를 풀게 된다면,  정확한 좌표값을 참조하는 것이 독자의 문제 해결에 도움이 될 것입니다. 

 

나머지는 전체 코드를 보면서 마무리하겠습니다.

 

class Solution {
    public static int calcDist(int location, int value){
        //값이 0이거나 현재 위치가 0이면 키보드 인덱스 값 11을 넣어준다. 
        if(value == 0){
            value = 11;
        }
        if(location == 0){
            location = 11;
        }
        //왼손, 오른손 좌표 구하기 
        //location-1을 해줘서 인덱스를 0base로 해줘야 자신으로부터 거리가 1부터시작이 아닌 0부터 시작한다.
        int locationX = (location-1)/3;
        int locationY = (location-1)%3;
        
        int valueX = (value-1)/3;
        int valueY = (value-1)%3;
        
        int result = Math.abs(locationX - valueX) + Math.abs(locationY-valueY);
        return result;
    }
    public String solution(int[] numbers, String hand) {
        String answer = "";
        int LHandPos=10;
        int RHandPos=12;
        for(int i=0; i<numbers.length; i++){
            //왼손이 움직이는 경우
            if(numbers[i] == 1 || numbers[i] == 4 || numbers[i] == 7){
                answer += "L";
                LHandPos = numbers[i]; 
            }
            //오른손이 움직이는 경우
            else if(numbers[i] == 3 || numbers[i] == 6 || numbers[i] == 9){
                answer += "R";
                RHandPos = numbers[i]; 
            }else {
                //거리 계산이 필요한 경우(키패드의 중간열인 경우)
                int leftDist  = calcDist(LHandPos, numbers[i]);
                int rightDist = calcDist(RHandPos, numbers[i]);
                //왼손이 더 멈. 오른손으로 눌러야 하는 경우
                if(leftDist > rightDist){
                    answer += "R";
                    RHandPos = numbers[i];                   
                }
                //오른손이 더 멈. 왼손으로 눌러야 하는 경우
                else if(leftDist < rightDist){
                    answer += "L";
                    LHandPos = numbers[i];
                }
                //양 손에서부터 거리가 같은 경우
                else{
                    if(hand.equals("right")){
                        answer += "R";
                        RHandPos = numbers[i];
                    }else{
                        answer += "L";
                        LHandPos = numbers[i];
                    }
                }
            }
        }
        return answer;
    }
}
public class EnterKeyPad {
    public static void main(String[] args) {
        Solution s = new Solution();
        int numbers[] = {1, 3, 4, 5, 8, 2, 1, 4, 5, 9, 5};
        String hand = "right";
        
        System.out.println(s.solution(numbers, hand));
    }
}
 

 

자료출처 : https://programmers.co.kr/learn/courses/30/lessons/67256