프로그래머스 lv2 조이스틱

문제 링크

조이스틱

풀이

class Solution {
    public int solution(String name) {
        int answer = 0;
        int move = name.length() - 1; // 정방향으로 움직였을 때는 글자 길이의 -1 만큼 움직인다.
        char[] chars = name.toCharArray();
        for (int i = 0; i < chars.length; i++) {
            // 알파벳 변형에 얼마나 비용이 필요한가? 를 계산
            answer += getChangeCnt(chars[i]);

            // 해당 인덱스 뒤로 만약에 A가 연속적으로 있다면 그만큼 개수를 세어준다.
            int idx = i + 1;
            while (idx < chars.length && chars[idx] == 'A') {
                idx += 1;
            }

            move = Math.min(move, i * 2 + chars.length - idx); // 앞에서부터 돌고 그 다음에 뒤로가는게 더 적은 움직임을 갖게되는 경우 (BBAAABBB)
            move = Math.min(move, i + (chars.length - idx) * 2); // 뒤에서부터 돌고 다시 돌아오는 경우가 더 적은 움직임을 갖게되는 경우 (BBBAAABB)
        }

        return answer + move;
    }

    // 상하로 움직이는 경우 (알파벳을 바꿀떄 필요)
    public int getChangeCnt(char a) {
        return Math.min(a - 'A', 'Z' - a + 1);
    }
}

해설

• 문제에서 알파벳을 변환하는 부분은 아주 간단하게 구할 수 있다.
  • A에서 Z방향으로 움직이면서 바꾸느냐, 아니면 A에서 바로 Z로 건너가서 역뱡향으로 움직이느냐 두 가지를 고려하면 된다.
  • ASCII 값으로는 대문자간에 1씩 차이가 난다. 그렇기에 이를 통해서 거리를 구할 수 있다.
  • A에서 Z 순으로 움직이면서 알파벳을 변경한 경우는 현재 문자 - 'A'
  • A에서 Z로 바로 넘어가서, 역방향으로 움직이는 경우에는 'Z' - a + 1 이다.
    (마지막 1은 A에서 바로 Z로 넘어가는 경우를 더해주는 것)
• 이 문제에서 가장 어려운 부분은 좌 우로 움직이는 부분이다. 관련되어서 다음과 같이 설명되어 있다.

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

  • 좌우로 자유롭게 이동이 가능하다.
  • 이 부분에서 가장 많이 헤맸다. 그래서 다른 사람이 남긴 힌트를 봤다.
  • 가장 쉽게 생각하는 방법은 가운데 A가 연속되어있다면 그 부분은 굳이 탐색을 하지 않아도 된다는 것이었다.
  • 예를 들어, BBAAABB 라고 주어진다면 가장 최소 탐색법은 다음과 같다. (이동만 따진다. 알파벳 변경은 위에서 처리한다)
    • B(0) -> B(1) - 1번
    • 다시 되돌아온다. B(1) -> B(0) - 1번
    • 마지막으로 이동한다. B(0) -> B(6) - 1번
    • 그 전으로 이동한다. B(6) -> B(5) - 1번
  • 앞에서부터 차례대로 이동했다면, 문자열의 길이 - 1 로 6번이지만, 위처럼 이동시에는 4번만 이동하면 된다.
  • 위의 움직임에서 규칙성을 찾으면 다음과 같다.
    • 앞에서부터 돌고, 그 다음에 뒤로가는 경우

      현재 인덱스 * 2 // 연속된 A를 만나기 전에 한번 왔다가 갔다가 하는 경우의 수
      + (전체 문자열 길이 - 마지막 연속된 A까지의 문자 길이) // 마지막으로 연속된 A 까지의 문자열을 제외한 나머지 이동거리

    • 첫글자에서 바로 뒤로가서 돈 뒤로, 다시 앞으로 와서 도는 경우

      현재 인덱스 // 연속된 A를 만나기전에 이동하는 경우의 수 
      + (전체 문자열 길이 - 마지막 연속된 A까지의 문자의 길이) * 2 // 마지막으로 연속된 A 까지의 문자열을 제외한 나머지 문자열 왔다 갔다하는 경우의 수

  • 이렇게 두 가지 경우의 수를 따져서 가장 적게 나오는 이동횟수를 따지면 원하는 이동횟수가 나온다.

소감

• 코테를 풀때 뭐부터 생각해야하는걸까.. 규칙성 찾기?
• 맨날 규칙성을 못찾고 헤매는 느낌이다.