[프로그래머스] 조이스틱(leve2, Greedy)

문제 설명

조이스틱으로 알파벳 이름을 완성하세요. 맨 처음엔 A로만 이루어져 있습니다.

ex) 완성해야 하는 이름이 세 글자면 AAA, 네 글자면 AAAA

 

조이스틱을 각 방향으로 움직이면 아래와 같습니다.

▲ - 다음 알파벳

▼ - 이전 알파벳 (A에서 아래쪽으로 이동하면 Z로)

◀ - 커서를 왼쪽으로 이동 (첫 번째 위치에서 왼쪽으로 이동하면 마지막 문자에 커서)

▶ - 커서를 오른쪽으로 이동 (마지막 위치에서 오른쪽으로 이동하면 첫 번째 문자에 커서)

예를 들어 아래의 방법으로 "JAZ"를 만들 수 있습니다.

 

• `첫 번째 위치에서 조이스틱을 위로 9번 조작하여 J를 완성합니다.
• 조이스틱을 왼쪽으로 1번 조작하여 커서를 마지막 문자 위치로 이동시킵니다.
• 마지막 위치에서 조이스틱을 아래로 1번 조작하여 Z를 완성합니다. 따라서 11번 이동시켜 "JAZ"를 만들 수 있고, 이때가 최소 이동입니다.`

만들고자 하는 이름 name이 매개변수로 주어질 때, 이름에 대해 조이스틱 조작 횟수의 최솟값을 return 하도록 solution 함수를 만드세요.

 

제한 사항

• name은 알파벳 대문자로만 이루어져 있습니다.
• name의 길이는 1 이상 20 이하입니다.

 

입출력 예

name	return
"JEROEN"	56
"JAN"	23

 

 

public int solution(String name) {
    int answer = 0; // 조이스틱 조작 횟수를 저장할 변수
    int len = name.length(); // 주어진 문자열의 길이
    int move = name.length() - 1; // 기본적으로 커서를 오른쪽으로 쭉 이동하는 경우의 최소 좌우 이동 횟수

    // 각 위치에서 해당 알파벳을 변경하기 위한 최솟값을 계산
    for (int i = 0; i < len; i++) {
        // 해당 알파벳을 'A'에서 원하는 알파벳으로 변경하기 위한 최소 조작 횟수를 더함
        // Math.min(name.charAt(i) - 'A', 'Z' - name.charAt(i) + 1):
        //  - 알파벳을 위로 이동 ('A' -> 'B' -> ...) 하는 경우와
        //  - 알파벳을 아래로 이동 ('A' -> 'Z' -> ...) 하는 경우 중 최소값을 선택
        answer += Math.min(name.charAt(i) - 'A', 'Z' - name.charAt(i) + 1);

        // 연속된 'A'가 끝나는 지점(next)을 찾음
        int next = i + 1;
        while (next < len && name.charAt(next) == 'A') {
            next++;
        }

        // 좌우 이동의 최소 횟수를 계산
        // (i * 2) + len - next:
        //  - 커서를 처음부터 오른쪽으로 이동하고 다시 왼쪽으로 돌아오는 경우
        // (len - next) * 2 + i:
        //  - 커서를 끝에서부터 왼쪽으로 이동하고 다시 오른쪽으로 돌아오는 경우
        move = Math.min(move, (i * 2) + len - next);
        move = Math.min(move, (len - next) * 2 + i);
    }

    answer += move; // 좌우 이동 최소 횟수를 총 조작 횟수에 더함
    return answer;
}

 

 

1) A와 Z 중 문자와 가까운 알파벳 찾기

name.charAt(i) - 'A'

 

조이스틱을 위쪽(다음 알파벳)으로 조작하는 경우

 

 

'Z' - name.charAt(i) + 1

 

조이스틱을 아래(이전 알파벳)로 조작하는 경우

 

 

2) 연속된 A가 끝나는 지점을 찾은 후 커서 이동을 최소화하는 방법 계산하기

        // 연속된 'A'가 끝나는 지점(next)을 찾음
        int next = i + 1;
        while (next < len && name.charAt(next) == 'A') {
            next++;
        }

        // 좌우 이동의 최소 횟수를 계산
        // (i * 2) + len - next:
        //  - 커서를 처음부터 오른쪽으로 이동하고 다시 왼쪽으로 돌아오는 경우
        // (len - next) * 2 + i:
        //  - 커서를 끝에서부터 왼쪽으로 이동하고 다시 오른쪽으로 돌아오는 경우
        move = Math.min(move, (i * 2) + len - next);
        move = Math.min(move, (len - next) * 2 + i);

 

커서 이동을 최소화하기 위해 연속된 A가 끝나는 지점을 찾도록 했다.

 

그리고 좌우 이동의 최소 횟수를 계산했다.

커서를 처음부터 오른쪽으로 이동하고 다시 왼쪽으로 돌아오는 경우를

(i * 2) + len - next 로 계산했는데 여기서 i * 2는 현재 위치 i에서 오른쪽으로 이동하다가 커서를 왼쪽으로 되돌려 이동하는 상황을 의미한다.

 

i만큼 오른쪽으로 갔다가 다시 되돌아와야 하기 때문에 i * 2만큼 이동하는 것이다.

 

되돌아간 후 연속된 A 뒤의 문자를 처리하기 위해 len - next 만큼 더 이동을 해야 한다.

 

(len - next) * 2 + 1은 끝에서부터 왼쪽으로 이동한 후 다시 오른쪽으로 돌아가는 상황이다.

끝에서 next 지점까지 이동한 후 다시 되돌아올 때 2 * (len -next)만큼의 이동이 필요하고

다시 현재 위치까지 이동할 때 i만큼 더 이동해야 한다.

 

 

참고

https://hstory0208.tistory.com/entry/Java자바-프로그래머스-Lv2-조이스틱-Greedy탐욕법