[프로그래머스 / Java] 코딩테스트 연습: 조이스틱 (그리디)

난이도: Level 2

문제: https://school.programmers.co.kr/learn/courses/30/lessons/42860

프로그래머스

---

 

그리디는 정말 어렵다......

그리디는 사고력 싸움이 아닐까?

정답 코드는 매우 짧지만 완전히 이해하는데 시간이 꽤 걸렸다.

 

우선 변수를 다음과 같이 선언한다.

move의 초기값은 오른쪽으로 쭉 순차적으로 탐색할 때의 이동 횟수이다.

 

    int answer = 0;     // 조이스틱 총 이동 횟수의 최솟값

    int length = name.length();     // name의 길이

    int move = length - 1;  // 조이스틱 좌우 이동 횟수의 최솟값

 

 

우선 상하 이동 횟수를 계산하는 것은 쉽다.

현재 알파벳에서 A만큼 뺀 횟수와 Z에서 현재 알파벳만큼 뺀 횟수에서 1 더한 값 중에 최솟값을 선택하면 된다.

 

    // name에 속한 문자를 모두 검사

    for (int i = 0; i < length; i++) {

        // 조이스틱 상하 이동 횟수 계산

        int up = name.charAt(i) - 'A';  // 다음 알파벳 이동 횟수

        int down = 'Z' - name.charAt(i) + 1;    // 이전 알파벳 이동 횟수

        answer += Math.min(up, down);   // 둘 중 더 작은 값을 더하기

 

 

문제는 좌우 이동 횟수를 계산하는 것이다.

이것이 레벨2라면 난 그리디를 절대 내 힘으로 짧은 시간 내에 못 풀 것 같다.

이 그림을 보고 오른쪽으로 갔다가 왼쪽으로 돌아가는 경우를 확실하게 이해할 수 있었다.

출처: https://excited-hyun.tistory.com/207

[프로그래머스 - Java] 조이스틱

 

이 그림에서 conA가 내 코드에서는 next가 된다.

이 분이 풀 때는 아래의 1번 경우만 테스트케이스에 포함되었던 것 같다.

그런데 내가 제출했을 때에는 오류가 났다.

그 이유는 2022년 이후에는 아래의 2번 경우도 테스트케이스에 추가되었기 때문이다.

 

1) 오른쪽으로 i만큼 이동했다가 다시 왼쪽으로 i만큼 돌아가고, 왼쪽으로 length - next만큼 이동하는 경우

move = Math.min(move, i * 2 + length - next)

 

2) 왼쪽으로 length - next만큼 이동했다가 다시 오른쪽으로 length - next만큼 돌아가고, 오른쪽으로 i만큼 이동하는 경우

move = Math.min(move, (length - next) * 2 + i)

 

    // name에 속한 문자를 모두 검사

    for (int i = 0; i < length; i++) {

        // 조이스틱 상하 이동 횟수 계산

        // (생략)

       

        // 조이스틱 좌우 이동 최솟값 계산

        int next = i + 1;  // 'A'가 위치하는 가장 마지막 인덱스 찾기

        // 현재 인덱스의 다음 인덱스가 name의 길이보다 작고,

        // 다음 인덱스에 해당하는 문자가 'A'라면

        while (next < length && name.charAt(next) == 'A') {

            next++;    // 다음 인덱스 1 증가

        }

       

        // 순서대로 가는 것과, 뒤로 돌아가는 것 중 이동수가 적은 것을 선택

        // i * 2를 하는 이유

        // => 오른쪽으로 i까지 이동했다가 다시 왼쪽으로 i만큼 돌아가야하므로

        move = Math.min(move, i * 2 + length - next);

        // BBBBAAAAAAAB와 같이 처음부터 뒷부분을 먼저 입력하는 것이 더 빠른 경우도 고려

        // (length - next) * 2를 하는 이유

        // => 왼쪽으로 length - next까지 이동했다가 다시 오른쪽으로 length - next만큼 돌아가야하므로

        move = Math.min(move, (length - next) * 2 + i);

    }

 

 

위 과정이 끝나면 move는 좌우 이동 횟수의 가장 최솟값이 된다.

이 값을 최종 리턴할 answer에 더한 후 리턴하면 된다.

 

    answer += move;     // 좌우 이동 횟수의 최솟값을 찾아서 answer에 더하기

   

    return answer;      // 조이스틱 이동 횟수의 최솟값 리턴

 

---

전체 코드

class Solution {
    public int solution(String name) {
        int answer = 0;     // 조이스틱 총 이동 횟수의 최솟값
        int length = name.length();     // name의 길이
        int move = length - 1;  // 조이스틱 좌우 이동 횟수의 최솟값
        
        // name에 속한 문자를 모두 검사
        for (int i = 0; i < length; i++) {
            // 조이스틱 상하 이동 횟수 계산
            int up = name.charAt(i) - 'A';  // 다음 알파벳 이동 횟수
            int down = 'Z' - name.charAt(i) + 1;    // 이전 알파벳 이동 횟수
            answer += Math.min(up, down);   // 둘 중 더 작은 값을 더하기
            
            // 조이스틱 좌우 이동 최솟값 계산
            int next = i + 1;  // 'A'가 위치하는 가장 마지막 인덱스 찾기
            // 현재 인덱스의 다음 인덱스가 name의 길이보다 작고,
            // 다음 인덱스에 해당하는 문자가 'A'라면
            while (next < length && name.charAt(next) == 'A') {
                next++;    // 다음 인덱스 1 증가
            }
            
            // 순서대로 가는 것과, 뒤로 돌아가는 것 중 이동수가 적은 것을 선택
            // i * 2를 하는 이유
            // => 오른쪽으로 i까지 이동했다가 다시 왼쪽으로 i만큼 돌아가야하므로
            move = Math.min(move, i * 2 + length - next);
            // BBBBAAAAAAAB와 같이 처음부터 뒷부분을 먼저 입력하는 것이 더 빠른 경우도 고려
            // (length - next) * 2를 하는 이유
            // => 왼쪽으로 length - next까지 이동했다가 다시 오른쪽으로 length - next만큼 돌아가야하므로 
            move = Math.min(move, (length - next) * 2 + i);
        }
        
        answer += move;     // 좌우 이동 횟수의 최솟값을 찾아서 answer에 더하기
        
        return answer;      // 조이스틱 이동 횟수의 최솟값 리턴
    }
}