[프로그래머스] 프로그래머스 Level1 키패드 누르기 Java (카카오 코딩테스트)

문제

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

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

풀이

구현 + BFS(최단거리)로 풀 수 있었다.

keyPad라는 2차원 배열을 만들어서 최단거리를 측정할 수 있도록 해주었고, 문자열으로 모든 번호의 좌표를 기록해주어 현재 손가락의 위치가 바뀔 때 마다 해당 문자열을 참조하여 위치를 업데이트 해주었다.

이후에는 문제의 의도대로 1, 4, 7일때 왼손가락, 3, 6, 9일때 오른손가락을 사용할 수 있도록 하고 나머지 2, 5, 8, 0에 대해서는 현재 왼손가락, 오른손가락의 위치와 해당 번호의 좌표를 참조하여 각각의 손가락에 대해 BFS로 최단거리를 측정해주었다. 각각의 최단거리를 얻었다면 다시 문제의 의도대로 더 가까운 손가락이 그 번호를 누를 수 있도록 해주고 해당 손가락의 위치를 업데이트 시켜주면 된다.

이러한 싸이클을 바탕으로 모든 numbers의 원소에 대해 반복하면 정답을 구할 수 있다.

문제를 풀면서 주의할 점은 매번 사용한 손가락의 위치가 바뀌기 때문에 위치를 계속 업데이트 시켜주는 것을 잊지말자.

코드

import java.util.LinkedList;
import java.util.Queue;

class Solution {

    final int[] dx = {1,0,-1,0};
    final int[] dy = {0,1,0,-1};

    int[][] keyPad = {
            {1,2,3},
            {4,5,6},
            {7,8,9},
            {-1,0,-1}
    };

    public String solution(int[] numbers, String hand) {

        String answer = "";
        String rightLoc = "32";
        String leftLoc = "30";
        String oneLoc = "00";
        String twoLoc = "01";
        String threeLoc = "02";
        String fourLoc = "10";
        String fiveLoc = "11";
        String sixLoc = "12";
        String sevenLoc = "20";
        String eightLoc = "21";
        String nineLoc = "22";
        String zeroLoc = "31";

        for(int i = 0; i < numbers.length; i++) {

            if(numbers[i] == 3 || numbers[i] == 6 || numbers[i] == 9) {
                switch (numbers[i]) {
                    case 3:
                        rightLoc = threeLoc;
                        break;
                    case 6:
                        rightLoc = sixLoc;
                        break;
                    case 9:
                        rightLoc = nineLoc;
                        break;
                }
                answer+= "R";
            } else if(numbers[i] == 1 || numbers[i] == 4 || numbers[i] == 7) {
                switch (numbers[i]) {
                    case 1:
                        leftLoc = oneLoc;
                        break;
                    case 4:
                        leftLoc = fourLoc;
                        break;
                    case 7:
                        leftLoc = sevenLoc;
                        break;
                }
                answer+= "L";
            } else {
                String targetLoc = "";
                int rx = Character.getNumericValue(rightLoc.charAt(0));
                int ry = Character.getNumericValue(rightLoc.charAt(1));
                int lx = Character.getNumericValue(leftLoc.charAt(0));
                int ly = Character.getNumericValue(leftLoc.charAt(1));
                if(numbers[i] == 2) {
                    targetLoc = twoLoc;
                    int tx = Character.getNumericValue(targetLoc.charAt(0));
                    int ty = Character.getNumericValue(targetLoc.charAt(1));
                    int leftDist = BFS(tx,ty,lx,ly);
                    int rightDist = BFS(tx,ty,rx,ry);
                    if(leftDist < rightDist) {
                        answer += "L";
                        leftLoc = targetLoc;
                    } else if(leftDist > rightDist) {
                        answer += "R";
                        rightLoc = targetLoc;
                    } else {
                        if(hand.equals("right")) {
                            answer += "R";
                            rightLoc = targetLoc;
                        } else {
                            answer += "L";
                            leftLoc = targetLoc;
                        }
                    }
                } else if(numbers[i] == 5) {
                    targetLoc = fiveLoc;
                    int tx = Character.getNumericValue(targetLoc.charAt(0));
                    int ty = Character.getNumericValue(targetLoc.charAt(1));
                    int leftDist = BFS(tx,ty,lx,ly);
                    int rightDist = BFS(tx,ty,rx,ry);
                    if(leftDist < rightDist) {
                        answer += "L";
                        leftLoc = targetLoc;
                    } else if(leftDist > rightDist) {
                        answer += "R";
                        rightLoc = targetLoc;
                    } else {
                        if(hand.equals("right")) {
                            answer += "R";
                            rightLoc = targetLoc;
                        } else {
                            answer += "L";
                            leftLoc = targetLoc;
                        }
                    }
                } else if(numbers[i] == 8) {
                    targetLoc = eightLoc;
                    int tx = Character.getNumericValue(targetLoc.charAt(0));
                    int ty = Character.getNumericValue(targetLoc.charAt(1));
                    int leftDist = BFS(tx,ty,lx,ly);
                    int rightDist = BFS(tx,ty,rx,ry);
                    if(leftDist < rightDist) {
                        answer += "L";
                        leftLoc = targetLoc;
                    } else if(leftDist > rightDist) {
                        answer += "R";
                        rightLoc = targetLoc;
                    } else {
                        if(hand.equals("right")) {
                            answer += "R";
                            rightLoc = targetLoc;
                        } else {
                            answer += "L";
                            leftLoc = targetLoc;
                        }
                    }
                } else if(numbers[i] == 0) {
                    targetLoc = zeroLoc;
                    int tx = Character.getNumericValue(targetLoc.charAt(0));
                    int ty = Character.getNumericValue(targetLoc.charAt(1));
                    int leftDist = BFS(tx,ty,lx,ly);
                    int rightDist = BFS(tx,ty,rx,ry);
                    if(leftDist < rightDist) {
                        answer += "L";
                        leftLoc = targetLoc;
                    } else if(leftDist > rightDist) {
                        answer += "R";
                        rightLoc = targetLoc;
                    } else {
                        if(hand.equals("right")) {
                            answer += "R";
                            rightLoc = targetLoc;
                        } else {
                            answer += "L";
                            leftLoc = targetLoc;
                        }
                    }
                }
            }
        }
        return answer;
    }

    int BFS(int targetX, int targetY, int startX, int startY) {
        if(targetX == startX && targetY == startY) {
            return 0;
        }
        int[][] dist = new int[4][3];
        for(int i = 0; i < 4; i++) {
            for(int j = 0; j < 3; j++) {
                dist[i][j] = -1;
            }
        }
        Queue<int[]> q = new LinkedList<>();
        q.add(new int[] {startX, startY});
        dist[startX][startY] = 0;

        while (!q.isEmpty()) {
            int cur[] = q.poll();
            int curX = cur[0];
            int curY = cur[1];

            for(int dir = 0; dir < 4; dir++) {
                int nx = curX + dx[dir];
                int ny = curY + dy[dir];

                if(nx < 0 || nx >= 4 || ny < 0 || ny >= 3) {
                    continue;
                }
                if(dist[nx][ny] != -1 || keyPad[nx][ny] == -1) {
                    continue;
                }

                q.add(new int[] {nx, ny});
                dist[nx][ny] = dist[curX][curY] + 1;
                if(nx == targetX && ny == targetY) {
                    return dist[targetX][targetY];
                }
            }
        }
        return 0;
    }
}