키패드 누르기(프로그래머스)

문제링크 : https://programmers.co.kr/learn/courses/30/lessons/67256

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

 

난이도 : 레벨 1

 

이 문제는 구현력 기르기에 적합한 문제라고 생각한다.

 

 

왼손과 오른손이 누를 수 있는 번호가 정해져 있다.

 

왼손은 1,4,7

오른손은 3,6,9

 

그러면 2,5,8,0은 ???

 

아쉽게도 2,5,8,0은 왼손과 오른손 모두 누를 수 있다..

중간영역의 숫자인 2,5,8,0을 어느 손으로 눌러야 하는지 매 상황마다 판단해야 한다.

전형적인 그리디 알고리즘 문제이다.

 

 

중간부분을 누르는 규칙을 찾아야 하는 문제인걸 직감했다.

 

그런데 나는 그렇게 안했다.

 

왜냐면 키패드의 개수는 고작 12개이다.

 

아예 룩업테이블을 만들어서 거리를 미리 넣어놓는다면..?

머리 아프게 규칙을 찾을 필요도 없고연산량도 조금 줄일 수 있다고 생각했다.

 

즉,

왼손 및 오른손의 위치에서 눌러야할 숫자까지의 거리를

2차원 배열에 미리 저장해두었다가

필요한 상황이 왔을때 저장된 값을 꺼내 쓰면 된다고 판단했다.

 

메모이제이션을 미리 해놓는다고 생각하면 된다. (라고 말하지만 사실 하드코딩)

 

 

예를 들어,

거리를 저장해둔 변수의 이름을 lookUp이라고 하면

 

lookUp[1][5]의 값은

키패드 1의 위치에서 키패드 5를 누르기 위한 거리이다.

 

처음에 왼손은 *, 오른손은 #에서 시작한다고 했으므로

 

왼손의 위치를 10(*)오른손의 위치를 11(#) 이라고 처음에 가정하면 된다.

 

 

아래는 코드이다.

 

class Solution {
    public String solution(int[] numbers, String hand) {
        String answer = "";
        
        int leftPosition = 10;
        int rightPosition = 11;
        
        int[][] lookUp = new int[12][10];
        
        // (1,4,7)에서 (2,5,8,0) 까지의 거리
        lookUp[1][2] = 1; lookUp[4][2] = 2; lookUp[7][2] = 3;
        lookUp[1][5] = 2; lookUp[4][5] = 1; lookUp[7][5] = 2;
        lookUp[1][8] = 3; lookUp[4][8] = 2; lookUp[7][8] = 1;
        lookUp[1][0] = 4; lookUp[4][0] = 3; lookUp[7][0] = 2;
        
        // (3,6,9)에서 (2,5,8,0) 까지의 거리
        lookUp[3][2] = 1; lookUp[6][2] = 2; lookUp[9][2] = 3;
        lookUp[3][5] = 2; lookUp[6][5] = 1; lookUp[9][5] = 2;
        lookUp[3][8] = 3; lookUp[6][8] = 2; lookUp[9][8] = 1;
        lookUp[3][0] = 4; lookUp[6][0] = 3; lookUp[9][0] = 2;
        
        // (2,5,8,0)에서 (2,5,8,0) 까지의 거리
        lookUp[2][2] = 0; lookUp[5][2] = 1; lookUp[8][2] = 2; lookUp[0][2] = 3;
        lookUp[2][5] = 1; lookUp[5][5] = 0; lookUp[8][5] = 1; lookUp[0][5] = 2;
        lookUp[2][8] = 2; lookUp[5][8] = 1; lookUp[8][8] = 0; lookUp[0][8] = 1;
        lookUp[2][0] = 3; lookUp[5][0] = 2; lookUp[8][0] = 1; lookUp[0][0] = 0;
        
        // (*,#)에서 (2,5,8,0) 까지의 거리
        lookUp[10][2] = 4; lookUp[11][2] = 4;
        lookUp[10][5] = 3; lookUp[11][5] = 3;
        lookUp[10][8] = 2; lookUp[11][8] = 2;
        lookUp[10][0] = 1; lookUp[11][0] = 1;
        
        for ( int i = 0; i < numbers.length; ++i) {
            if ( numbers[i] == 1 || numbers[i] == 4 || numbers[i] == 7) {
                answer += "L";
                leftPosition = numbers[i];
                
            } else if ( numbers[i] == 3 || numbers[i] == 6 || numbers[i] == 9) {
                answer += "R";
                rightPosition = numbers[i];
                
            } else {
                if ( lookUp[leftPosition][numbers[i]] < lookUp[rightPosition][numbers[i]]) {
                    answer += "L";
                    leftPosition = numbers[i];
                    
                } else if ( lookUp[leftPosition][numbers[i]] > lookUp[rightPosition][numbers[i]]) {
                    answer += "R";
                    rightPosition = numbers[i];
                    
                } else {
                    if ( "left".equals(hand)) {
                        answer += "L";
                        leftPosition = numbers[i];
                        
                    } else {
                        answer += "R";
                        rightPosition = numbers[i];
                        
                    }
                }
            }
        }
        
        return answer;
    }
}

미리 저장해둔 값을 사용했기 때문에

로직이 간단해진다.

 

다만, 저렇게 짜면 공간복잡도는 당연히 올라간다.

공간을 더 쓰는 대신 연산을 줄인 것이다.

 

시간복잡도는 O(N) 이다.

 

마지막으로

저 코드는 최적화된 코드가 아니다.

가장 먼저 생각났던 해결방법을 기술한 것이다.