[프로그래머스] 레벨2 조이스틱

https://programmers.co.kr/learn/courses/30/lessons/42860?language=java# 

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

 

이 문제는 구현하기에 따라 어떻게 보면 그리디 알고리즘이고, 또 어떻게 브루트포스 같은 구현 문제인 것 같다. 사실 이 두 개를 굳이 분류하는 것도 딱 나뉘어서 분류하다기보다는 적절히 두 개념이 섞여있다고 생각한다.

 

1. 일단 함수의 인자로 받는 파라미터 name의 길이가 1이면 옆으로 움직일 필요없이 바로 'A'에서 빼서 예외처리를 해준다.

2. 이외의 경우에는 모든 글자값에 대한 반환체크를 위해 isChange 배열을 선언해서 초기값 모두 true로 설정해준다.

     2-1. isChange의 배열을 탐색하는 searchIndex를 선언하여, 각 배열의 앞/뒤 기준으로 변환이 안된 글자를 찾도록 설정하여 각각 값들을 배열의 1, 2번째 인덱스 값으로 반환한다.

3. 반복문의 종료 조건은 모든 글자가 바뀔 때까지로 설정하며, 아직 바꿀 글자가 있을 경우에는 조이스틱을 움직일 케이스를 3가지로 나눠 처리한 후 결과를 리턴한다.

     3-1. Case 1 → 방향으로 갈 때 : 현재 글자를 가리키는 인덱스보다 큰 배열 인덱스가 아직 바뀌지 않았을 경우에는 무조건 앞 방향으로 인덱스를 바꿔준다.

     3-2-1. Case 2 단순히 왼쪽 ← 방향으로 갈 때 : searchIndex의 결과 backward가 현재 인덱스보다 작을 경우에는 무조건 뒤 방향으로 인덱스를 바꿔준다.

     3-2-2. Case 3 맨 왼쪽에서 맨 오른쪽 ← 방향으로 갈 때 : 약간의 예외적인 상황으로 현재 인덱스를 기준으로 forward, backward의 거리를 각각 계산해서 backward가 더 가까울 경우 맨 오른쪽으로 인덱스를 바꿔준다.

     3-3. 이 때 모든 인덱스의 변화는 이동거리에 전부 더해준다.

     3-4. 바꿔준 인덱스를 기준으로 글자 값을 찾아 'A'에서 빼주고 이동거리를 늘려준다. 이 때, 'Z'가 바꿀 값일 경우에는 25가 아니라 1이 나와야한다.

 

 

---

문제 및 입출력

 

---

코드

import java.util.Arrays;

public class Solution
{
     // 정방향, 역방향 인덱스 기준으로 바뀐 글자가 있는 지 확인
     public static int[] searchIndex(boolean[] arr, int start)
     {
         int forward = 0;
         int backward = 0;

         // 앞에서부터 확인
         for(int i=start; i<arr.length; i++)
         {
             if(!arr[i])
             {
                 forward = i;
                 break;
             }
         }
         // 뒤에서부터 확인
         for(int i=arr.length-1; i>=0; i--)
         {
             if(!arr[i])
             {
                 backward = i;
                 break;
             }
         }

         return new int[] {forward, backward};
     }
     public static int solution(String name)
    {
         if(name.length()==1)
         {
             return Math.min(name.charAt(0)-'A', 'A'-name.charAt(0)+26);
         }

         int answer = 0;
         int now_index = 0;
         final char a = 'A';

         // A가 아닌 글자찾아서 배열 설정
         boolean[] isChange = new boolean[name.length()];
         Arrays.fill(isChange, false);

         for(int i=0; i<name.length(); i++)
         {
             if(name.charAt(i)=='A')
             {
                 isChange[i] = true; 
             }
         }

         while(true)
         {
              int forward = searchIndex(isChange, now_index)[0];
              int backward = searchIndex(isChange, now_index)[1];

              // 모든 글자가 바뀔 떄까지 반복
              if(forward+backward==0)
              {
                   break;
              }

              // case 1 : → 방향으로 갈 때
              if(forward>=now_index && forward-now_index<=now_index+name.length()-backward)
              {
                   answer += Math.abs(forward-now_index);
                   now_index = forward;
              }
              // case 2 : ← 방향으로 갈 때
              else
              {
                   if(backward<now_index) // case 2-1 : 단순 오른쪽에서 왼쪽으로
                   {
                        answer += Math.abs(now_index-backward);
                   }
                   else // case 2-2 : 맨 왼쪽에서 오른쪽으로
                   {
                        answer += Math.abs(now_index+name.length()-backward);
                   }

                   now_index = backward;
              }

              // 글자를 바꿀 인덱스를 찾은 후, 변경
              char input_char = name.charAt(now_index);

              // 'Z'-'A' => 'A-'Z'+26인 반대로 뺄 때
              if(input_char-a>a-input_char+26)
              {
                   answer +=  a-input_char+26;
              }
              // 'B'-'A'처럼 일반적인 상황
              else
              {
                   answer += input_char-a;
              }

              isChange[now_index] = true;
        }

        return answer;
    }
}