230127 TIL (알고리즘, 리팩토링)

알고리즘

키패드 누르기

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

프로그래머스

 

나의 풀이

계속 조금씩 생각하며 작성했는데 정말 오래 걸렸다. 이차원 배열을 사용해야 할지 아니면 그냥 일차원 배열에서 해결해야 하는지 고민 했었는데, 이차원 배열을 사용해도 일일히 비교를 해야 한다는 것은 변함이 없는 것 같아서 일차원 배열을 사용하는 것으로 결정 하였다.

일정한 공식이 있는지 생각해 보았지만, 특별한 것이 생각나지 않았다. 하나하나 노가다로 푸는 것보다 그나마 거리를 계산해서 하는 것이 조금 더 일정한 패턴이 있는 것을 발견하였다. 버튼 수의 차이의 절대값을 구하고 절대값에 따라 거리가 일정하게 차이나는 것을 반환하는 getCount 메소드를 만들어 주고, 왼손과 오른손의 거리를 비교하여 짧은 손의 글자를 넣어주는 방법으로 진행하였다.

public static int getDistance(int n, int hand) {
    int subtract = Math.abs(n - hand);
    return switch (subtract) {
        case 1, 3 -> 1;
        case 2, 4, 6 -> 2;
        case 5, 7, 9 -> 3;
        case 8, 10 -> 4;
        default -> 0;
    };
}

public String solution(int[] numbers, String hand) {
    String answer = "";
    int left = 10;
    int right = 12;
    for (int n : numbers) {
        if (n == 1 || n == 4 || n == 7) {
            answer += "L";
            left = n;
        }
        if (n == 3 || n == 6 || n == 9) {
            answer += "R";
            right = n;
        }
        if (n == 2 || n == 5 || n == 8 || n == 0) {
            if (n == 0) n = 11;
            int lDistance = getDistance(n, left);
            int rDistance = getDistance(n, right);
            if (lDistance == rDistance && hand.equals("left") || lDistance < rDistance) {
                answer += "L";
                left = n;
            } else {
                answer += "R";
                right = n;
            }
        }
    }
    return answer;
}

1, 4, 7 버튼의 경우는 무조건 왼손으로 누르고, 3, 6, 9 버튼은 무조건 오른손으로 누르므로 각각의 손의 글자를 넣어주는 조건문을 작성하고 2, 5, 8, 0의 경우 왼손과 오른손의 위치에 따라 거리가 가까운 손으로 누르게 되므로 직전에 왼손과 오른손의 위치를 left 와 right 변수에 넣어주고 거리를 구하는 메소드를 사용하여 왼손과 오른손의 거리를 구하고 왼손과 오른손의 거리를 비교하여 가까운 손의 글자를 넣어준다.

0의 경우는 위의 메소드로 거리를 구하면 절대값이 달라져서 작성한 메소드를 사용할 수 없게 되어 0인 경우의 메소드를 따로 만들어 주었다가 코드가 너무 길어지고 비효율적인 것 같아 0의 위치의 수를 11로 변경하고 왼손 시작점의 *을 10, 오른손 시작점의 #을 12로 설정하여 0인 경우의 절대값도, 시작할 때의 절대값도 일관성을 두었다.

다른 사람의 풀이

다른 사람들의 풀이를 보다가 버튼의 위치를 좌표화 하여 풀어나간 방식이 눈에 띄었다. 위의 풀이 방식으로는 현재 방법에는 적합해 보여도 범위가 유동적이거나 한 줄당 갯수가 달라지면 적용하지 못할듯 싶어서 좌표화 하여 푸는 방식을 알아두는게 좋을듯 하다.

class Solution {
    // 0부터 9까지 좌표 {y,x}
    int[][] numpadPos = {
            {3,1}, //0
            {0,0}, //1
            {0,1}, //2
            {0,2}, //3
            {1,0}, //4
            {1,1}, //5
            {1,2}, //6
            {2,0}, //7
            {2,1}, //8
            {2,2}  //9
    };
    // 초기 위치
    int[] leftPos = {3,0};
    int[] rightPos = {3,2};
    String hand;
    public String solution(int[] numbers, String hand) {
        this.hand = (hand.equals("right")) ? "R" : "L";

        String answer = "";
        for (int num : numbers) {
            String Umji = pushNumber(num);
            answer += Umji;

            if(Umji.equals("L")) {leftPos = numpadPos[num]; continue;}
            if(Umji.equals("R")) {rightPos = numpadPos[num]; continue;}
        }
        return answer;
    }

    // num버튼을 누를 때 어디 손을 사용하는가
    private String pushNumber(int num) {
        if(num==1 || num==4 || num==7) return "L";
        if(num==3 || num==6 || num==9) return "R";

        // 2,5,8,0 일때 어디 손가락이 가까운가
        if(getDist(leftPos, num) > getDist(rightPos, num)) return "R";
        if(getDist(leftPos, num) < getDist(rightPos, num)) return "L";

        // 같으면 손잡이
        return this.hand;
    }

    // 해당 위치와 번호 위치의 거리
    private int getDist(int[] pos, int num) {
        return Math.abs(pos[0]-numpadPos[num][0]) + Math.abs(pos[1]-numpadPos[num][1]);
    }
}

풀이법의 작성자가 주석으로 자세하게 설명을 달아둬서 이해하기가 쉬웠다. 좌표를 모두 설정하여 좌표간의 거리를 구하는 방법 중 하나인 맨해튼 거리 개념으로 좌표간의 거리를 구하고 비교하여 푸는 방식이었다.

맨해튼 거리 개념은 (a, b) 좌표와 (c, d) 좌표 간의 거리를 구할 때 |(a - c)| + |(b - d)| 로 구하는 방식이라고 한다. 맨해튼 거리 개념 이외에 유클리드 거리 개념도 있었는데, 유클리드 거리 개념은 (a, b) 좌표와 (c, d) 좌표 간의 거리를 구할 때 (a - c)^2 + (b - d)^2 을 구하고 그 제곱근으로 구하는 방법이 있다고 한다.

위의 코드를 유클리드 거리 식으로 바꾸면 다음과 같이 작성할 수 있다.

// 해당 위치와 번호 위치의 거리
    private int getDist(int[] pos, int num) {
        return Math.sqrt(Math.pow(pos[0]-numpadPos[num][0], 2) + Math.pow(pos[1]-numpadPos[num][1], 2));
    }

다음에 비슷한 유형의 문제를 마주치면 좌표를 이용한 방식으로 풀어보아야 할 것이다.

---