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

키패드 누르기 풀이 | 맨해튼 거리 완전 정리

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

1. 문제 설명

스마트폰 키패드에서 숫자를 입력할 때
왼손과 오른손 중 어떤 손을 사용할지 판단하는 문제

조건은 다음과 같음

• 1 4 7 은 무조건 왼손 사용
• 3 6 9 는 무조건 오른손 사용
• 2 5 8 0 은 현재 손 위치 기준 더 가까운 손 사용
• 거리가 같으면 주 손잡이 사용

단순 구현처럼 보이지만
현재 손 위치가 계속 변경되기 때문에
상태 관리가 핵심인 시뮬레이션 문제

---

2. 핵심 아이디어

이 문제 핵심은 키패드를 좌표처럼 관리하는 방식

키패드를 아래처럼 좌표로 변환 가능

1 -> (0,0)
2 -> (0,1)
3 -> (0,2)

4 -> (1,0)
5 -> (1,1)
6 -> (1,2)

7 -> (2,0)
8 -> (2,1)
9 -> (2,2)

* -> (3,0)
0 -> (3,1)
# -> (3,2)

이제 손가락 위치와 목표 숫자의 위치 차이만 계산하면 해결 가능

---

3. 맨해튼 거리 방식 설명

이 문제는 대각선 이동 불가능

즉

• 위
• 아래
• 왼쪽
• 오른쪽

이동만 가능

그래서 사용하는 방식이 "맨해튼 거리"

공식은 다음과 같음

|x_1-x_2|+|y_1-y_2|

---

예시

현재 왼손 위치

4 -> (1,0)

목표 숫자

8 -> (2,1)

거리 계산

|1-2|+|0-1|=2

즉

• 아래로 1칸 이동
• 오른쪽으로 1칸 이동

총 2칸 이동 필요

이 방식으로 왼손과 오른손 거리 비교 진행

---

4. 풀이 방법 비교

하드코딩 방식

숫자마다 이동 거리 직접 계산 방식

단점

• 조건 많아짐
• 유지보수 어려움
• 실수 위험 큼

---

좌표 기반 거리 계산 방식

숫자를 좌표로 변환 후 거리 계산 방식

장점

• 코드 가독성 좋음
• 규칙 명확
• 유지보수 쉬움
• 거리 계산 공통 처리 가능
• 실수 감소

이 문제에서는 좌표 방식이 가장 안정적인 선택

---

5. 최적 풀이 선택 이유

좌표 기반 방식 선택 이유

• 거리 계산 로직 통일 가능
• 상태 관리 명확
• 분기 최소화 가능
• 시간복잡도 O(N)

numbers 배열 최대 크기는 1000

배열 한 번만 순회하면 해결 가능

실전 코딩테스트 기준에서도
가장 안전하고 구현 실수 적은 구조

---

6. Java 코드

class Solution {

    /*
     * 숫자 키패드 위치 저장 배열
     *
     * index = 숫자
     * value = {행, 열}
     *
     * 예시
     * 1 -> {0,0}
     * 5 -> {1,1}
     * 0 -> {3,1}
     *
     * 좌표처럼 관리하면
     * 거리 계산을 공통 로직으로 처리 가능
     */
    private static final int[][] KEY_POSITION = {
            {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
    };

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

        /*
         * 결과 문자열 저장용 객체
         *
         * String += 연산 사용 시
         * 문자열 객체가 계속 새로 생성됨
         *
         * StringBuilder 사용으로
         * 메모리 사용량과 성능 최적화 가능
         */
        StringBuilder result = new StringBuilder(numbers.length);

        /*
         * 현재 왼손 위치
         *
         * 시작 위치는 *
         * 좌표로는 (3,0)
         */
        int leftRow = 3;
        int leftCol = 0;

        /*
         * 현재 오른손 위치
         *
         * 시작 위치는 #
         * 좌표로는 (3,2)
         */
        int rightRow = 3;
        int rightCol = 2;

        /*
         * 주 손잡이 여부 저장
         *
         * 반복문마다 문자열 비교하지 않기 위해
         * boolean 값으로 미리 저장
         */
        boolean isRightHand = hand.equals("right");

        /*
         * numbers 배열을 처음부터 끝까지 순회
         *
         * 숫자를 하나씩 확인하면서
         * 어떤 손을 사용할지 결정
         */
        for (int number : numbers) {

            /*
             * 1 4 7 은 무조건 왼손 사용
             */
            if (number == 1 || number == 4 || number == 7) {

                result.append('L');

                // 왼손 위치 최신화
                leftRow = KEY_POSITION[number][0];
                leftCol = KEY_POSITION[number][1];

                continue;
            }

            /*
             * 3 6 9 는 무조건 오른손 사용
             */
            if (number == 3 || number == 6 || number == 9) {

                result.append('R');

                // 오른손 위치 최신화
                rightRow = KEY_POSITION[number][0];
                rightCol = KEY_POSITION[number][1];

                continue;
            }

            /*
             * 가운데 숫자 처리 구간
             *
             * 2 5 8 0 은
             * 현재 손 위치 기준 더 가까운 손 사용
             */

            // 목표 숫자의 좌표 저장
            int targetRow = KEY_POSITION[number][0];
            int targetCol = KEY_POSITION[number][1];

            /*
             * 맨해튼 거리 계산 방식 사용
             *
             * 공식
             * |행 차이| + |열 차이|
             *
             * 이유
             * 이 문제는 대각선 이동 불가능
             * 상하좌우 이동만 가능하기 때문
             */

            // 왼손 거리 계산
            int leftDistance =
                    Math.abs(leftRow - targetRow)
                            + Math.abs(leftCol - targetCol);

            // 오른손 거리 계산
            int rightDistance =
                    Math.abs(rightRow - targetRow)
                            + Math.abs(rightCol - targetCol);

            /*
             * 왼손이 더 가까운 경우
             */
            if (leftDistance < rightDistance) {

                result.append('L');

                // 왼손 위치 이동
                leftRow = targetRow;
                leftCol = targetCol;
            }

            /*
             * 오른손이 더 가까운 경우
             */
            else if (leftDistance > rightDistance) {

                result.append('R');

                // 오른손 위치 이동
                rightRow = targetRow;
                rightCol = targetCol;
            }

            /*
             * 거리가 같은 경우
             *
             * 주 손잡이 사용
             */
            else {

                // 오른손잡이인 경우
                if (isRightHand) {

                    result.append('R');

                    rightRow = targetRow;
                    rightCol = targetCol;
                }

                // 왼손잡이인 경우
                else {

                    result.append('L');

                    leftRow = targetRow;
                    leftCol = targetCol;
                }
            }
        }

        return result.toString();
    }
}

 

---

7. 시간복잡도 & 공간복잡도

시간복잡도

O(N)

numbers 배열 한 번만 순회

---

공간복잡도

O(1)

고정 크기 배열만 사용

추가 메모리 거의 없음

---

8. 최적화 포인트

• StringBuilder 사용으로 문자열 생성 비용 제거
• 좌표 배열 static final 처리
• 문자열 비교 1회만 수행
• continue 사용으로 분기 단순화
• 거리 계산 공통 처리
• 추가 객체 생성 제거

실전 코딩테스트에서는
이런 작은 최적화 차이도 실행시간 차이로 이어지는 경우 많음

---

9. 마무리 정리

이 문제 핵심은 상태 관리

특히

• 현재 손 위치 갱신
• 거리 계산
• 조건 분기 처리

이 흐름을 정확하게 구현하는 연습 문제

그리고 맨해튼 거리 방식은
코딩테스트에서 정말 자주 등장하는 개념

• BFS
• 최단거리
• 격자 탐색
• 시뮬레이션

같은 유형에서도 계속 사용되는 핵심 개념

반드시 익숙해질 필요 있는 풀이 방식