[Algorithm] 키패드 누르기

<프로그래머스> 키패드 누르기

• 맨해튼 거리 구하는 방법을 응용하여 코딩하면 된다.

• 맨해튼 거리란?
  두 점 사이의 거리를 측정하는 방법 중 하나로, 두 점 감의 수평 이동 및 수직 이동 거리를 합산하여 계산한다.

초록색 선은 유클리드 거리이다.
나머지는 모두 총길이가 같다는 함정이 있는데 이것이 바로 맨해튼 거리이다.

맨해튼 거리는 두 지점 간의 "도시 블록" 을 따라 이동하는 것과 같은 움직임을 모델링한다.
때때로 "L1 거리" 또는 "도시 블록 거리" 로도 불린다.

두 점 A(x1, y1)와 B(x2, y2) 간의 맨해튼 거리는 다음과 같이 계산된다:

Manhattan Distance = |x1 - x2| + |y1 - y2|

이것은 x 좌표 간의 차이를 계산하고, 그 다음 y 좌표 간의 차이를 계산한 다음 두 차이를 더한 것이다.

java 에서 맨해튼 거리를 계산하는 간단한 예시 코드는 아래와 같다.

public class ManhattanDistanceCalculator {

    public static int calculateManhattanDistance(int x1, int y1, int x2, int y2) {
        int deltaX = Math.abs(x1 - x2);
        int deltaY = Math.abs(y1 - y2);
        return deltaX + deltaY;
    }

    public static void main(String[] args) {
        int x1 = 1;
        int y1 = 2;
        int x2 = 4;
        int y2 = 6;

        int manhattanDistance = calculateManhattanDistance(x1, y1, x2, y2);
        System.out.println("맨해튼 거리: " + manhattanDistance);
    }
}

이 공식을 활용해서 <키패드 누르기> 문제를 풀어보면 다음과 같다.

• Math.abs() : 절대값을 구하는 함수

public class Solution {
	public String solution(int[] numbers, String hand) {
		String answer = "";
        // 초기에 왼손이 *에, 오른손이 #에 있는 것을 각각 10, 12로 치환하였다
		int left = 10;
		int right = 12;

		StringBuilder sb = new StringBuilder();

		for (int number : numbers) {
        	// 숫자 1, 4, 7을 누를 때 조건
			if (number == 1 || number == 4 || number == 7) {
				sb.append("L");
				left = number;
           	// 숫자 1, 4, 7을 누를 때 조건
			} else if (number == 3 || number == 6 || number == 9) {
				sb.append("R");
				right = number;
            // 숫자 0을 누를 때 조건
			} else {
				if (number == 0) {
                	// 숫자 0은 11로 치환한다
					number = 11;
				}
                // 키패드 위아래로 3차이, 양옆으로 1차이인 것을 이용해서 아래와 같이 거리를 구하는 식을 이용해서 푼다
				int leftDist = Math.abs(number - left) / 3 + Math.abs(number - left) % 3;
				int rightDist = Math.abs(number - right) / 3 + Math.abs(number - right) % 3;

				// 오른손, 왼손 중 거리가 짧은 것을 도출
				if (leftDist < rightDist) {
					sb.append("L");
					left = number;
				} else if (leftDist > rightDist) {
					sb.append("R");
					right = number;
                // 오른손, 왼손 거리가 같다면 무슨 손잡이인지를 확인 후 도출
				} else {
					if (hand.equals("left")) {
						sb.append("L");
						left = number;
					} else {
						sb.append("R");
						right = number;
					}
				}
			}
		}
		answer = sb.toString();

		return answer;
	}
}

참고