[Java] level2 - greedy_42839 : 조이스틱

문제 링크

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

풀이

로직

상하 움직임

• A가 아닌 값은 위아래로 몇번 움직이면 되는지 구하면 된다
• A~Z까지 diff에 위 or 아래로 몇번 움직이는게 최단인지 담아둔다.
  • diff 길이가 알파벳 갯수와 동일하고
  • diff의 idx는 알파벳에서의 idx와 동일 => diff에서 idx 1번은 B를 의미, idx 25번은 Z를 의미

int answer = 0;
int[] diff={0,1,2,3,4,5,6,7,8,9,10,11,12,13,12,11,10,9,8,7,6,5,4,3,2,1}; // A~Z까지 몇번 움직여야하는지 나타냄
                                                                         // N(13) 다음부터는 거꾸로 움직이는게 빨라 숫자가 작아짐
// 상하 움직임 계산하는 부분
for(char c:name.toCharArray())
    answer+=diff[c-'A']; // A로부터의 위아래로 조이스틱을 몇번 움직여야하는지를 계산해줌

좌우 움직임

• 좌우 움직임을 가져가려면 1) 우측 + 우측되돌아가기 + 좌측, 2) 좌측 + 좌측되돌아가기 + 우측 이 두가지가 우측으로만 움직였을때 보다 작아야한다.
  • 맨앞쪽 or 맨뒤쪽 연속된 A가 있을경우 => 우측으로만 움직이거나, 좌측으로만 움직이거나 하면된다.
    • (참고) 맨앞쪽에 연속된 A가 있는 경우는 아래 코드에서 좌측으로 움직이는 경운 i=0인 경우로 고려됨
    • 즉, 우측 0회 + 우측되돌아가기 0회 + 좌측 n회 이렇게 계산되니 => 좌측으로만 몇회 움직였는지로 계산됨
  • 중간에 A가 있는 경우 => 이경우가 좌우로 모두 움직임 가져가야하는 경우임

int length=name.length();
        int min=length-1; // 초기값이 length-1인 이유는 우측으로만 움직였을때 length-1번이면 모든 글자들 다 훑을 수 있음

        for(int i=0;i<length;i++){
            int next=i+1;
            while(next<length && name.charAt(next)=='A'){ // 다음글자가 A이면 오른쪽으로 넘어가기때문에 next++해줌
                next++;
            }
            // min에는 최소한의 좌우 움직임이 몇번인지 담기게됨
              // i : 우측 움직임 횟수
              // length - next : 좌측 움직임 횟수(거꾸로)
              // i + length-next + Math.min(i, length-next) :  좌측/우측 움직임 + 되돌아오는 횟수 <- 이때 되돌아 오는 횟수는 좌측/우측 중 작은 횟수
              // Math.min(min, i + length-next + Math.min(i, length-next) )
                // => 단순히 우측으로만 움직이는 것과 좌측/우측 왔다갔다하면서 움직이는 것 중 가장 더 적게 움직이는 횟수 택하게됨
            min = Math.min(min, i + length-next + Math.min(i, length-next) );