문제 출처: https://programmers.co.kr/learn/courses/30/lessons/67256

문제 설명

1, 2, 3
4, 5, 6
7, 8, 9
*, 0, #

키패드에서

1, 4, 7은 왼손,
3, 6, 9는 오른손,
중간의 2, 5, 8, 0은 둘중 가까운 손(거리가 같다면 주 손잡이 우선순위)

이렇게 해서

numbers

[1, 3, 4, 5, 8, 2, 1, 4, 5, 9, 5]

hand

"right"

numbers 와 hand가 입력값으로 오면

"LRLLLRLLRRL" 같은 String을 출력해주면 된다.

내 문제 풀이

import java.util.*;

class Solution {
    public String solution(int[] numbers, String hand) {        
        HashMap <Integer, Integer[]> keypad = new HashMap<>();
        keypad.put(0, new Integer[] {8});
        keypad.put(1, new Integer[] {2, 4});
        keypad.put(2, new Integer[] {1, 3, 5});
        keypad.put(3, new Integer[] {2, 6});
        keypad.put(4, new Integer[] {1, 5, 7});
        keypad.put(5, new Integer[] {2, 4, 6, 8});
        keypad.put(6, new Integer[] {3, 5, 9});
        keypad.put(7, new Integer[] {4, 8});
        keypad.put(8, new Integer[] {0, 5, 7, 9});
        keypad.put(9, new Integer[] {6, 8});
        keypad.put(10, new Integer[] {0, 7}); //*
        keypad.put(11, new Integer[] {0, 9}); //#
        
        int left = 10;
        int right = 11;
        StringBuilder sb = new StringBuilder();
        
        for(int i = 0; i < numbers.length; i++) {
            Integer [] leftfix = {1, 4, 7};
            Integer [] rightfix = {3, 6, 9};
            if(Arrays.asList(leftfix).contains(numbers[i])) {
                left = numbers[i];
                sb.append("L");
            } else if (Arrays.asList(rightfix).contains(numbers[i])) {
                right = numbers[i];
                sb.append("R");
            } else {
                boolean[] visited = new boolean[12];
                int rightFar = howFar(keypad, right, numbers[i], 0, visited);
                visited = new boolean[12];
                int leftFar = howFar(keypad, left, numbers[i], 0, visited);              
                if(rightFar == leftFar) {
                    if(hand.equals("left")){
                        left = numbers[i];
                        sb.append("L");
                    } else {
                        right = numbers[i];
                        sb.append("R");
                    }
                } else if (rightFar < leftFar) {
                    right = numbers[i];
                    sb.append("R");
                } else {
                    left = numbers[i];
                    sb.append("L");
                }
            }
        }
        return sb.toString();
    }
    
    public int howFar(HashMap<Integer, Integer[]> keypad, int current, int target, int count, boolean [] visited) {
        
        if(current == target) {
            return count;
        }else {
            if(!visited[current]){
                int[] vals = Arrays.stream(keypad.get(current)).mapToInt(Integer::intValue).toArray();
                visited[current] = true;
                if(vals.length == 1) {
                    return howFar(keypad, vals[0], target, count + 1, visited);
                } else if(vals.length == 2) {
                    return Math.min(howFar(keypad, vals[0], target, count + 1, visited), howFar(keypad, vals[1], target, count + 1, Arrays.copyOf(visited, visited.length)));
                } else if(vals.length == 3) {
                    return Math.min(howFar(keypad, vals[2], target, count + 1, visited), Math.min(howFar(keypad, vals[0], target, count + 1, Arrays.copyOf(visited, visited.length)), howFar(keypad, vals[1], target, count + 1, Arrays.copyOf(visited, visited.length))));
                } else {
                     return Math.min(Math.min(howFar(keypad, vals[0], target, count + 1, visited), howFar(keypad, vals[1], target, count + 1, Arrays.copyOf(visited, visited.length))), Math.min(howFar(keypad, vals[2], target, count + 1, Arrays.copyOf(visited, visited.length)), howFar(keypad, vals[3], target, count + 1, Arrays.copyOf(visited, visited.length))));
                }
            }
        }
        return 100;
    }
}

문제를 처음에 잘 못 이해해서 HashMap을 만든 후 완전탐색을 해버렸다... (성능 안좋음)

Integer [] leftfix = {1, 4, 7};
            Integer [] rightfix = {3, 6, 9};
            if(Arrays.asList(leftfix).contains(numbers[i])) {
                left = numbers[i];
                sb.append("L");
            } else if (Arrays.asList(rightfix).contains(numbers[i])) {
                right = numbers[i];
                sb.append("R");
            }

이 부분만 넣어 주니 통과....

새로 알게 된것

• Arrays.copyOf(visited, visited.length) 이렇게 배열의 카피를 넣어줘야 call by value 처럼 적용되지 않아 배열로 현재 위치에 맞추어 트래킹이 가능하다.

• Arrays.asList(leftfix).contains(numbers[i]) 는 Integer[] 로 해야 가능하다. char[] 역시 Character로 해야 가능하다.

• array를 맵에 value로 넣고 싶으면 keypad.put(0, new Integer[] {8}) 이렇게 해야 된다.

스터디 함께한 팀원의 풀이[출처]

class Solution {
    public int distance(int num, int pos){
        int distance = 100;
        int temp_num = 100;

        if (pos % 3 == 2) {
            temp_num = Math.abs(num - pos);
        }else if (pos % 3 == 1) {
            temp_num = Math.abs(num - pos);
        }else if(pos %3 == 0){
            temp_num = Math.abs(num - (pos - 2));
        }

        distance = getDist(temp_num);

        return distance;
    }
    public int getDist(int num){
        int distance = 0;

        while (num > 0) {
            if (num - 3 >= 0) {
                num -= 3;
                distance++;
            } else if (num == 1) {
                num -= 1;
                distance++;
            } else {
                distance += 2;
                num = 0;
            }
        }

        return distance;
    }
    public int nowLocZeroDist(int num){
        // num이 0일땐 거리가 0이므로 기본값 0 반환
        int distance = 0;

        if (num == 8) {
            distance = 1;
        } else if (num == 5) {
            distance = 2;
        } else if (num == 2) {
            distance = 3;
        }

        return distance;
    }
    public int objNumIsZero(int pos){
        int distance = 0;

        switch (pos) {
            case 1:         case 3:
                distance = 4; break;
            case 4: case 2: case 6:
                distance = 3; break;
            case 7: case 5: case 9:
                distance = 2; break;
                    case 8: case -1:
                distance = 1; break;
            case 0:
                distance = 0; break;
        }

        return distance;
    }
    public int nowLocDefault(int num){
        // num이 0일땐 거리가 0이므로 기본값 0 반환
        int distance = 0;

        if (num == 8) {
            distance = 2;
        } else if (num == 5) {
            distance = 3;
        } else if (num == 2) {
            distance = 4;
        }

        return distance;
    }

    public String solution(int[] numbers, String hand) {
        // 1 4 7이면 L
        // 3 6 9면 R
        // 2 5 8 0은 현재 위치에서 가까운 손
        // 거리가 같을 경우 hand에 의존

        StringBuilder answer = new StringBuilder();
        int lPos = -1;
        int rPos = -1;

        for (int num : numbers) {
            if (num == 1 || num == 4 || num == 7) {
                // 1 4 7일 경우 왼 손
                lPos = num;
                answer.append("L");
            } else if (num == 3 || num == 6 || num == 9) {
                // 3 6 9일 경우 오른손
                rPos = num;
                answer.append("R");
            } else {
                // 거리 계산을 위한 변수
                // 0을 대상으로 하지 않은 거리 구하기
                int lDist = distance(num, lPos);
                int rDist = distance(num, rPos);

                // 현재 위치가 0 또는 기본값(*, #)일 경우
                if (lPos == 0) {
                    lDist = nowLocZeroDist(num);
                }else if(lPos == -1){
                    lDist = nowLocDefault(num);
                }
                if (rPos == 0) {
                    rDist = nowLocZeroDist(num);
                }else if(rPos == -1){
                    rDist = nowLocDefault(num);
                }

                // 목표가 0일 경우
                if (num == 0) {
                    lDist = objNumIsZero(lPos);
                    rDist = objNumIsZero(rPos);
                }

                // 출력구간
                if (lDist < rDist) {
                    lPos = num;
                    answer.append("L");
                } else if (lDist > rDist) {
                    rPos = num;
                    answer.append("R");
                } else {
                    if (hand.equals("left")) {
                        lPos = num;
                        answer.append("L");
                    } else {
                        rPos = num;
                        answer.append("R");
                    }
                }

            }
        }
        return answer.toString();
    }
}

코드가 좀 길긴 하지만 성능면을 고려 했을때 좋고 패턴을 찾아서 생각하신게 직관적이여서 가져와 봤다.

위아래 이동은 +3 오른쪽왼쪽 이동은 +1 이라는 규칙을 이용해 어차피 현재 위치에서 다음 키패드 위치로의 거리만 산출하면 되기때문에, 3, 6, 9를 1, 4, 7로 숫자를 바꾸어서 더하기 빼기로 거리를 구하셨다. 0의 위치만 패턴이 적용이 안되서 스위치 문으로 엣지 케이스 처리를 해주셨다고 하는데 잘하신것 같다.