[Lv.1] 키패드 누르기 : Java

프로그래머스

 

 

 

 

이해하기

처음엔 문제 내용 중 상하좌우 4가지 방향으로 이동 가능하고 이동하는 한 칸의 거리는 1이라는 점을 보고 BFS 문제인가? 생각하고 접근하였다. 그치만 도저히 BFS로 안 풀리는데 싶어서 접근 방법을 바꿔보았다.

 

아래 코드가 두번째 풀이이다.

class Solution {
    static int[][] numArr = {{1, 2, 3}, {4, 5, 6}, {7, 8, 9}, {-1, 0, -2}};
    int[] dX = {1, -1, 0, 0};
    int[] dY = {0, 0, 1, -1};

    public String solution(int[] numbers, String hand) {
        String answer = "";
        String leftSide = "147*";
        String rightSide = "369#";

        int[] leftIdx = {3, 0};
        int[] rightIdx = {3, 2};

        boolean[][] visited = new boolean[numArr.length][numArr[0].length];
        for (int i = 0; i < visited.length; i++) {
            for (int j = 0; j < visited[i].length; j++) {
                if (j == 0 || j == 2) {
                    visited[i][j] = true;
                }
            }
        }

        for (int i = 0; i < numbers.length; i++) {
            String cur = String.valueOf(numbers[i]);
            if (leftSide.contains(cur)) {
                answer += "L";
                leftIdx = findIdx(cur);
            } else if (rightSide.contains(cur)) {
                answer += "R";
                rightIdx = findIdx(cur);
            } else {
                double leftDistance = calDistance(leftIdx, cur);
                double rightDistance = calDistance(rightIdx, cur);
                if (leftDistance < rightDistance) {
                    answer += "L";
                    leftIdx = findIdx(cur);
                } else if (rightDistance < leftDistance) {
                    answer += "R";
                    rightIdx = findIdx(cur);
                } else {
                    if (hand.equals("right")) {
                        answer += "R";
                        rightIdx = findIdx(cur);
                    } else {
                        answer += "L";
                        leftIdx = findIdx(cur);
                    }
                }
            }
        }

        return answer;
    }
	public int[] findIdx(String cur) {
        int num = Integer.valueOf(cur);
        for (int i = 0; i < numArr.length; i++) {
            for (int j = 0; j < numArr[i].length; j++) {
                if (num == numArr[i][j]) {
                    return new int[]{i, j};
                }
            }
        }
        return new int[]{0, 0};
    }

    public double calDistance(int[] nowIdx, String cur) {
        int[] targetIdx = findIdx(cur);
        return (Math.pow((nowIdx[0] - targetIdx[0]), 2) + Math.pow((nowIdx[1] - targetIdx[1]), 2));
    }
}

 

1. 키패드 모양대로 numArr라는 2차원 배열을 만들어두고
2. 사방탐색을 위한 dX와 dY를 만들어둔다.
3. 방문처리를 위한 visited 배열도 만들고
4. 왼쪽 "1, 4, 7" 또는 오른쪽 "3, 6, 9"에 포함되지 않는 숫자에 대해서 leftDistance와 rightDistance를 구한다.
   1. 구하는 식은 그래프에서 점과 점 사이의 거리를 구하는 식으로 구했다... (아마 이 부분이 틀린 요인일 듯 하다.)
5. leftDistance > rightDistance면 오른손으로 누르도록
6. rightDistance > leftDistance면 왼손으로 누르도록
7. 둘이 거리가 같다면 어느 손잡이냐에 따라서 처리하도록 한다.

결과는 테스트 12/20 통과 = 60점

 

어떻게 고쳐야할지 감이 안 와서 다른 블로그를 참고했다.

[프로그래머스 Level1] 키패드 누르기 (JAVA) - 2020 Kakao

위 블로그에서 설명하기로는 거리를 구할 때 다음과 같은 식을 사용한다.

 

'현재 위치 - 누르는 위치'의 절대값 / 3 + '현재 위치 - 누르는 위치'의 절대값 % 3

 

여기서 '현재 위치 - 누르는 위치'의 절대값 / 3 은 상하거리, '현재 위치 - 누르는 위치'의 절대값 % 3 는 좌우거리라고 하는데... 이 식이 너무 이해가 안 돼서 직접 그려보았다!

 

 

목표 숫자가 8, 왼손의 현재 위치가 4, 오른손의 현재 위치가 3인 예시이다.

 

왼손부터 계산해보자.

|(8 - 4)| / 3 + |(8 - 4)| % 3 = 1 + 1 = 2

 

오른손 계산이다.

|(8 - 3)| / 3 + |(8 - 3)| % 3 = 5 / 3 + 5 % 3 = 1 + 2 = 3

 

상하거리를 계산할 때 /3 을 해주는 이유는 상하 값의 차이가 3이기 때문이다 (e.g. 3, 6, 9)

좌우거리를 계산할 때 %3을 해주는 이유는 좌우 값의 차이는 1이기 때문이다. (e.g. 1, 2, 3)

 

뭔가 알 듯 말 듯...

 

 

문제풀이

class Solution {
    public String solution(int[] numbers, String hand) {
                StringBuffer sb = new StringBuffer();
        String leftSide = "147";
        String rightSide = "369";
        String center = "2580";

        int left = 10;
        int right = 12;

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

            if (leftSide.contains(n + "")) {
                left = n;
                sb.append("L");
            }
            if (rightSide.contains(n + "")) {
                right = n;
                sb.append("R");
            }
            if (center.contains(n + "")) {
                if (n == 0) {
                    n = 11;
                }

                int leftDistance = (Math.abs(n - left) / 3 + Math.abs(n - left) % 3);
                int rightDistance = (Math.abs(n - right) / 3 + Math.abs(n - right) % 3);

                if (leftDistance == rightDistance) {
                    if (hand.equals("right")) {
                        right = n;
                        sb.append("R");
                    } else {
                        left = n;
                        sb.append("L");
                    }
                } else if (leftDistance > rightDistance) {
                    right = n;
                    sb.append("R");
                } else {
                    left = n;
                    sb.append("L");
                }
            }
        }

        return sb.toString();
    }
}

 

        StringBuffer sb = new StringBuffer();
        String leftSide = "147";
        String rightSide = "369";
        String center = "2580";

 

답을 저장할 sb를 선언하고, leftSide, rightSide, center에 해당하는 값들을 문자열로 만들어준다.

 

        int left = 10;
        int right = 12;

 

현재 왼손은 * 을 누르고 있는데 이를 10으로 친다.

오른손은 #을 누르고 있는데 이를 12로 친다.

 

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

            if (leftSide.contains(n + "")) {
                left = n;
                sb.append("L");
            }
            if (rightSide.contains(n + "")) {
                right = n;
                sb.append("R");
            }

 

numbers 배열을 순회하면서 n값이 왼쪽에 해당하면 left = n으로 바꿔주고 "L"을 append해준다.

n값이 오른쪽에 해당하면 right = n으로 바꿔주고 "R"을 append해준다.

 

            if (center.contains(n + "")) {
                if (n == 0) {
                    n = 11;
                }

 

만약 n값이 center에 해당한다면 세번째 if문 내부를 실행하게 되는데, 이 때 0은 11로 바꿔준다.

계산의 편의를 위해 * = 10, 0 = 11, # = 12로 바꾼 것이다.

 

                int leftDistance = (Math.abs(n - left) / 3 + Math.abs(n - left) % 3);
                int rightDistance = (Math.abs(n - right) / 3 + Math.abs(n - right) % 3);

                if (leftDistance == rightDistance) {
                    if (hand.equals("right")) {
                        right = n;
                        sb.append("R");
                    } else {
                        left = n;
                        sb.append("L");
                    }
                } else if (leftDistance > rightDistance) {
                    right = n;
                    sb.append("R");
                } else {
                    left = n;
                    sb.append("L");
                }

 

위에서 보았던 식을 적용해서 각각 거리를 구해주고 이를 비교하여 왼손 또는 오른손으로 누르게 한다.

 

 

쉽게 풀 수 있을 줄 알았는데 생각보다 이해하는데 오래 걸렸던 문제... 이게 Lv.1이라니...