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

문제 소개

• Level 2
• https://school.programmers.co.kr/learn/courses/30/lessons/42860
• 테스트케이스 (추가)
  • “BBAAAAB” / 6

풀이

public int solution(String name) {
    int count = 0;
    int length = name.length();
    int move = length-1; // 순서대로 가는 이동 수
    char[] chars = name.toCharArray();
    for (int i = 0; i < length; i++) { // 65 ~ 90, 총 26개
        if (chars[i] != 'A') {
            count += Math.min(chars[i]-'A', 'Z'-chars[i]+1); // +1은 A->Z로 이동
        }

        int next = i+1;
        while (next < length && chars[next] == 'A') {
            next ++;
        }
        move = Math.min(move, i*2+length-next); // 순서대로 가는 이동 수와, 뒤로 돌아가는 이동 수 중 더 적은 것을 선택
        move = Math.min(move, (length-next)*2 + i); // 처음부터 뒷부분을 먼저 입력하는 것이 더 빠른 경우도 고려
    }

    return count + move;
}

처음에는 알파벳을 조정하는 조이스틱인 상, 하에 대한 요소만 신경 쓰다가 틀리게 된 문제이다.

좌, 우를 계산하여 합칠 아이디어가 도무지 생각나지 않아서 결국에는 찾아보았다.

가장 중요한 두 로직이 복잡해 보여 자세히 풀어 이해해보기 위해 글을 작성하였다.

• i*2+length-next
  • i*2 : 현재까지 이동한 거리 + 되돌아갈 거리
  • length-next : 처음 인덱스에서 연속된 A의 마지막 인덱스 까지의 거리
• (length-next)*2 + i
  • (length-next)*2 : 처음 인덱스에서 연속된 A의 마지막 인덱스 까지의 거리 + 이를 되돌아갈 거리
  • i : 이후 처음 A가 나오는 지점까지 이동할 거리

이처럼 A가 나왔을 때, 역방향으로 탐색할 지 아니면 계속 전진할 지를 `i*2+length-next`를 통해 결정하면 된다.

또한, 이 때 처음부터 역방향을 먼저 탐색한 후 정방향으로 탐색할 지를 ` (length-next)*2 + i`를 통해 검사하는 것이다.

---

https://yummy0102.tistory.com/359

[탐욕법(Greedy)] 조이스틱 - JAVA