[프로그래머스,Level 1] 키패드 누르기(JAVA 구현)

- 첫 풀이

  처음에는 이 문제에서 가운데 번호를 누르기 위해서 왼쪽, 오른쪽 손의 거리 차이에 따라 누루는 손이 결정된다는 것을 보고 bfs를 이용해 풀어보려고 했지만, 잘 해결되지 않아 검색을 통해 다른 분들의 풀이를 참고하였다.

 

- 정답풀이

  다른 분들의 주된 풀이로는 '맨해튼 거리 측정법'이었다. 관련 내용에 대해 간단히 찾아본 결과 맨해튼 거리 측정법은 유클리드 거리 측정법과는 다르게 점 A와 점 B의 사이에 장애물이 존재해 정해진 경로로만 이동이 가능하다는 차이점이 존재한다. 예를들어 왼손이 1번에 위치한 상태에서 5번을 누르기 위해서는 1-> 2-> 5 또는 1-> 4-> 5와 같이 대각선으로의 직접적인 이동이 불가능한 경우를 말한다. 맨해튼 거리 측정법의 공식은 |각 점의 X좌표 차이| + |각 점의 Y좌표 차이|로 구할 수 있다고 한다. 

 

+) 유클리드 거리 측정법은 우리가 알고 있는 피타고라스의 정리를 이용하는 방법으로 두 점 사이에 장애물이 존재하지 않아 대각선의 직접 거리를 재는 방법이라고 한다. 맨해튼 거리 측정법은 장애물이 존재하기 때문에 유클리드 거리 측정법의 결과보다 무조건 같거나 클 수밖에 없다고 한다.

 

  거리를 구하는 공식을 알았으므로, 각 번호들의 좌표를 어떻게 구해야 할 지 생각해보았다. X좌표의 경우는 키패드의 특성상 3씩 다음 좌표로 이동된다는 특성을 이용한다. 이때 3의 배수인 3,6,9를 잘 고려해 공식을 세우면 (N-1)/3을 통해 X좌표를 구할 수 있다. Y좌표 역시 위 과정을 통해서 (N-1)%3을 통해 구할 수 있다. 이제 이것들을 이용해 풀이를 진행하면 된다.

 

class Solution {
   public String solution(int[] numbers, String hand) {
        String answer = "";
        
        // 1. 좌표를 구하기 위해 *은 10, 0은 11, #은 12로 생각한다.
        int left = 10;
        int right = 12;
        
        // 2. 누르는 횟수만큼 반복.
        for(int i = 0;i<numbers.length;i++){
            // 2-1. 1,4,7은 왼손으로 누르고 왼손의 위치를 갱신한다.
            if(numbers[i] == 1 || numbers[i] == 4||numbers[i] == 7){                
                answer+="L";
                left = numbers[i];
                continue;
            // 2-2. 3,6,9는 오른손으로 누르고 오른손의 위치를 갱신한다.
            }else if(numbers[i] == 3 || numbers[i] == 6||numbers[i] == 9){
                answer+="R";
                right = numbers[i];
                continue;  
            // 2-3. 중앙의 번호들은 거리에 따라 누르게 된다.
            }else{
                // 2-3-1. 중앙의 0이면 번호는 11로 생각하며 아니면 해당 번호를 대입한다.
                int x = numbers[i] == 0 ? 11 : numbers[i];
                // 2-3-2. 왼손과 오른손으로부터 중앙의 번호와의 거리를 맨해튼 거리 측정법으로 구한다.
                int l_length = Math.abs((x-1)/3 - (left-1)/3) + Math.abs((x-1)%3 - (left-1)%3);
                int r_length = Math.abs((x-1)/3 - (right-1)/3) + Math.abs((x-1)%3 - (right-1)%3);
                // 2-3-3. 구한 거리가 같은 경우 hand에 따라 갱신해준다.
                if(l_length == r_length) {                    
                    if(hand.equals("right")){
                        answer+="R";
                        right = x;
                    }else{
                        answer+="L";
                        left=x;
                    }                
                }               
                // 2-3-4. 왼손으로부터의 거리가 짧은 경우는 왼손을, 오른손으로부터의 거리가 짧은 경우는 오른손을 갱신한다.
                else {
                    if(l_length<r_length){
                        answer+="L";
                        left=x;
                    }else{
                        answer+="R";
                        right=x; 
                    }
                }
            }                
        }
       
        return answer;
    }
}