조이스틱

https://programmers.co.kr/learn/courses/30/lessons/42860#

코딩테스트 연습 - 조이스틱

 

문제 설명

조이스틱으로 알파벳 이름을 완성하세요. 맨 처음엔 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

문제회고

나한테 있어서 조이스틱문제는 좌/우 처리가 상당히 까다로웠던 문제였다.
그나마 위안을 삼자면 대략적으로 생각했던 로직은 맞았는데, 그것을 구체화 시키는 부분에서 사실상 실패하고 다른 사람 풀이를 슬쩍 보고 이해한 뒤 코드를 작성하였다.

"BBBAAAAAABA" 이런 입력이 들어왔을 경우를 생각해보자. 답은 10이 출력되어야한다.
위의 경우는 (시작 - 커서는 카운팅 안됨.)B -> B -> B 이렇게 하면 다음으로 'A'를 만나게 된다.
우리는 이상황에서 2가지의 경우를 생각해볼 수 있다. 
1) 그냥 쭉 'A'를 카운팅하며 지나가는 경우
2) 반대로 돌아서 카운팅하는 경우
이렇게 두가지를 고려해서 카운팅 수가 작은 것을 선택하면 된다.

1번의 경우처럼 그냥 쭉 가는경우 커서 카운트는 길이 - 1이 될 것이다.
2번의 경우는 계산이 필요하다. 위의 예제에서는 2번의 경우가 6으로 더 작기 때문에 2번 경우를 선택하여야한다.

그래서 다시 'A'를 만나게 되는 지점으로 돌아가보면 다시 되돌아 가야한다. <- B <- B 를 해주면 다시 처음으로 온다.
카운트 값은 4가 된다. 이를 다시 공식화 시켜보면 (i + i) 가 되는 것이다. 즉 갔다가 'A'를 만나고 다시 뒤돌아오는 경우인 것이다.

제자리 돌아와서 우리는 뒤로 돌아가야한다. [B : 현재]BBAAAAAA[B : 목표 위치]A 
현재 처음 위치에서 목표위치까지의 커서의 위치를 생각해보면 "길이 - 다음 위치 인덱스(돌아가기전의 인덱스(2) + 1)" 를 돌아온 커서의 카운트값 4에다 더해주면 되는 것이다.

이때 이값이 전체 길이보다 더 커버린다면 우리는 1번의 쭉 진행하는 방식을 택하면 된다.
여기서 전체 길이는 '10'이지만 되돌아가면  '6'이 되므로 '6'을 선택하는 것이 합리적이다.

여기까지 이해를 하고 코드를 보면 이해가 될 것이다.

코드

class Solution {
    public int solution(String name) {
        
        int answer = 0;
        int len = name.length();
        int min = len - 1;
        
        for ( int i = 0; i < len; ++i ) {
            
            // 상/하 이동
            char c  = name.charAt( i );
            int num = Math.min( (c - 'A'), ('Z' - c + 1) );
            answer += num;
            
            // 커서처리 : 'A'를 만나면 계속 커서를 이동시켜준다.
            int next = i + 1;
            while ( next < len && name.charAt( next ) == 'A' ) ++next;
            
            // 좌/우 처리
            min = Math.min( min, (i + i) + (len - next) );
        }
        
        return answer + min;
    }
}