프로그래머스 - 키패드 누르기 [2020 카카오 인턴십] - Java

 

https://programmers.co.kr/learn/courses/30/lessons/67256#

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

 

키패드를 배열 삼아 오른쪽과 같이 배치를 했다.

 

{1,0}에서 {2,1}로 이동하기 위해서는 '맨해튼 거리 측정법' 을 이용한다.

거리 = | 현재 위치의 x 좌표값 - 이동할 위치의 x 좌표값 | + | 현재 위치의 y 좌표값 - 이동할 위치의 y 좌표값 |

 

* 만일 대각선 이동도 가능하다면 '유클리드 거리 측정법'을 이용한다. (피타고라스 정리 대각선)

 

거리가 같으면 오른손잡이냐 왼손잡이냐를 보고 지정한다.

 

(+) 키패드를 배열로 변환하는 과정에서 나는 HashMap을 사용했지만,

다른 사람들의 풀이를 보니 수학적으로 계산이 가능했다.

x좌표 = 키패드 숫자/3

y좌표 = (키패드 숫자-1)%3

 

ex) 키패드 숫자 == 7 일 때,  x좌표 는 7/3=2 , y좌표는 (7-1)%3=0 이다.

어떻게 이렇게 바로 떠오를 수가 있지?! 신기하다

 

<통과 코드>

import java.util.*;

class Solution {
    public static Integer left[] = new Integer[]{3,0};
    public static Integer right[] = new Integer[]{3,2}; //왼손, 오른손 위치
    public static HashMap<Integer,Integer[]> keypad = new HashMap<Integer,Integer[]>(); //숫자별 키패드 좌표
    public static int dx[] = {1,0,-1,0};
    public static int dy[] = {0,1,0,-1};
    // public static boolean visit[][] = new boolean[4][3];
    
    public String solution(int[] numbers, String hand) {
        String answer = "";
        
        
        
        //숫자별 키패드 좌표넣기
        keypad.put(0,new Integer[]{3,1});
        int row = 0; 
        int col = 0;
        for(int i=1;i<10;i++){
            if(col==3){
                row++;
                col=0;
            }
            keypad.put(i,new Integer[] {row,col++});
        }
        
        //number에 따라 누른 손가락 처리
        for(int i=0;i<numbers.length;i++) {
            int num = numbers[i];
            Integer goal[] = keypad.get(num);
            String str ="";
            
            //손위치 출력
            // System.out.println("누를 버튼: "+num);
            // System.out.println("left: {"+left[0]+","+left[1]+"} ");
            // System.out.println("right: {"+right[0]+","+right[1]+"} ");
            // System.out.println("====================================");
            
            switch(num){
                case 1: case 4: case 7:
                    str ="L";
                    break;
                case 3: case 6: case 9:
                    str ="R";
                    break;
                case 2: case 5: case 8: case 0: //2,5,8,0만 처리
                    int L_distance = Math.abs(left[0]-goal[0])+Math.abs(left[1]-goal[1]);
                    int R_distance = Math.abs(right[0]-goal[0])+Math.abs(right[1]-goal[1]);
                    if(L_distance==R_distance) {
                        str = (hand.equals("left")) ? "L" : "R";
                    } else {
                        str = (L_distance < R_distance) ? "L" : "R";
                    }
                    break;
            }
            
            //손가락 위치 변경
            if(str.equals("L"))
                left = goal;
            else
                right = goal;
            
            answer+=str;
        }
        
        

        return answer;
    }
    

}

 

 

 

<에러 코드>

최단거리라는 단어만 보고 bfs를 떠올려서 bfs대로 구현했다가 테스트케이스 13,15,16,20에서 실패가 났다.

import java.util.*;

class Solution {
    public static Integer left[] = new Integer[]{3,0};
    public static Integer right[] = new Integer[]{3,2}; //왼손, 오른손 위치
    public static HashMap<Integer,Integer[]> keypad = new HashMap<Integer,Integer[]>(); //숫자별 키패드 좌표
    public static int dx[] = {1,0,-1,0};
    public static int dy[] = {0,1,0,-1};
    // public static boolean visit[][] = new boolean[4][3];
    
    public String solution(int[] numbers, String hand) {
        String answer = "";
        
        
        
        //숫자별 키패드 좌표넣기
        keypad.put(0,new Integer[]{3,1});
        int row = 0; 
        int col = 0;
        for(int i=1;i<10;i++){
            if(col==3){
                row++;
                col=0;
            }
            keypad.put(i,new Integer[] {row,col++});
        }
        
        //number에 따라 누른 손가락 처리
        for(int i=0;i<numbers.length;i++) {
            int num = numbers[i];
            String str ="";
            
            //손위치 출력
            // System.out.println("누를 버튼: "+num);
            // System.out.println("left: {"+left[0]+","+left[1]+"} ");
            // System.out.println("right: {"+right[0]+","+right[1]+"} ");
            // System.out.println("====================================");
            
            switch(num){
                case 1: case 4: case 7:
                    str ="L";
                    break;
                case 3: case 6: case 9:
                    str ="R";
                    break;
                case 2: case 5: case 8: case 0: //2,5,8,0만 처리
                    String h = (hand.equals("right")) ? "R" : "L";
                    str =bfs(num,h);
                    break;
            }
            
            //손가락 위치 변경
            Integer goal[] = keypad.get(num);
            if(str.equals("L"))
                left = goal;
            else
                right = goal;
            
            answer+=str;
        }
        
        

        return answer;
    }
    
    
    public String bfs(Integer num, String hand) {
        Queue<Integer[]> q = new LinkedList<Integer[]>();
        boolean visit[][] = new boolean[4][3];
        boolean isLeft = false;
        boolean isRight = false;
        //해당 숫자에 도착한 최단거리
        //왼,오 거리가 같으면 자주쓰는 손으로 처리
        
        //눌러야할 숫자의 좌표위치
        Integer goal[] = keypad.get(num);
        int Ldistance = 999;
        int Rdistance = 999;
        
        //이미 그 번호 위에 손가락이 있는가?
        if(left[0]==goal[0] && left[1]==goal[1])
            return "L";
        else if(right[0]==goal[0] && right[1]==goal[1])
            return "R";
        
        //시작점 넣기
        q.add(new Integer[]{0,left[0],left[1],0}); //이동하는 손(left-0, right-1), 현재 위치, 이동횟수
        q.add(new Integer[]{1,right[0],right[1],0});
        
        // System.out.println("!!");
        
        //이동하자!
        //큐가 빌때까지
        while(!q.isEmpty()){
            Integer pos[] = q.poll();
            
            int dir = pos[0];
            int row = pos[1];
            int col = pos[2];
            int cnt = pos[3];
            
            //이미 최단거리 계산 끝난 방향인가?
            if(dir==0 && isLeft)
                continue;
            else if(dir==1 && isRight)
                continue;
            
            //한칸씩 이동
            for(int i =0;i<4;i++){
                int nx = row +dx[i];
                int ny = col +dy[i];
                
                if(nx>= 4 || nx <0 || ny >=3 || ny <0)
                    continue;
                

                
                // System.out.println("도착전,"+dir+", {"+nx+","+ny+"}, "+(cnt+1));
                // 도착했는가?
                if(nx==goal[0] && ny==goal[1]){
                    if(dir==0){
                        Ldistance = cnt+1;
                        isLeft= true;
                    } else {
                        Rdistance = cnt+1;
                        isRight = true;
                    }
                    
                    break;
                }
                
                if(visit[nx][ny])
                    continue;
                    
                visit[nx][ny]=true;
                // System.out.println(dir+", {"+nx+","+ny+"}, "+(cnt+1));
                q.add(new Integer[]{dir,nx,ny,cnt+1});    
            }
            
        }
    
    if(Ldistance==Rdistance)
        return hand;
    else if(Ldistance<Rdistance)
        return "L";
    else
        return "R";
        
        
        
    }
}