[프로그래머스] 42860번 : 조이스틱

코드

public class PRO_42860 {
    public static int solution(String name) {
        int answer = 0;
        int length = name.length();
        int minLength = length - 1;

        for (int i = 0; i < length; i++) {
            // 상, 하 이동
            char c = name.charAt(i);
            if (c - 'A' >= 13) answer += 'Z' - c + 1;
            else answer += c - 'A';

            //좌, 우 이동
            int next = i + 1;
            while (next < length && name.charAt(next) == 'A') ++next;

            minLength = Math.min(minLength, i + length - next + Math.min(i, length - next));
        }
        answer += minLength;
        return answer;
    }

    public static void main(String[] args) {
        String name1 = "JEROEN";
        String name2 = "JAN";

        System.out.println(solution(name1));
        System.out.println(solution(name2));
    }
}

풀이 및 느낀점

총 3단계로 문제에 접근했다.

1. 상, 하 이동 횟수
2. 좌, 우 이동 횟수
3. 1 + 2 = 전체 이동 횟수

1. 상, 하 이동 횟수

만약 현재 알파벳이 C(아스키코드: 67)라고 하면, A에서 아래로 이동하는 것보다 위로 이동하는 것이 덜 이동하는 것이므로 'C(67)-A(65)'라는 식을 이용하여 최소값 3을 구했다.

또한, 만약 현재 알파벳이 X(아스키코드:88)라고 하면, A에서 위로 이동하는 것보다 아래로 이동하는 것이 덜 이동하는 것이므로 'Z(90)-X(88)+1'라는 식을 이용하여 최소값 3을 구했다.

알파벳은 총 25가지이고 중간인 13을 기준으로 조건식을 만들었다.

2. 좌, 우 이동 횟수

현재 값의 바로 다음 값 위치를 next로 입력받았다. next가 전체길이보다 작고 동시에 next 위치의 값이 A라면 next를 증가시킨다.
모두 증가된 next는 연속된 A의 마지막 위치(인덱스) 값이다.

minLength = Math.min(minLength, i + length - next + Math.min(i, length - next));

위의 코드를 만드는 것이 어려웠다. 이해한 방식을 설명하겠다.

' A B A B A A A A A A A B A '라는 값을 입력받았다고 가정하고 이 값의 길이는 13이다.
연속된 A 직전의 값인 B의 위치(인덱스)는 3, 연속된 A 이후의 값인 B의 위치(인덱스)는 11이다.

총 2가지의 방법으로 이동할 수 있는데,

1번째는 0 -> 3 -> 0 - >11 ( i + i + (n-ind) )
2번째는 0 -> 11 -> 0 -> 3 ( (n-ind) + (n-ind) + i )

이다.

(i를 현재 위치, n은 전체 길이, ind는 연속된 전체 A 다음의 값 위치로 설정했다.)

이 2가지의 방법을 이용하여 둘 중에서 최소값을 구한다면, 좌우 이동 횟수를 구할 수 있다.

min( 2i + n - ind, i + 2n - ind ) = min( i, n - ind ) + (i + n - ind)

• (i + n - ind) : 전체 길이 - 연속하는 A

참고자료