조이스틱

🔗문제 링크

구현 코드

import java.util.*;
class Solution {
    public int solution(String name) {
        int answer = 0;
        int len = name.length();
        int min_move = len-1; //조이스틱을 움직여서 가질 수 있는 가장 큰 이동값 = 차례로 움직여서 len까지 가는 경우 
          
        for(int i=0;i<len;i++){
            //알파벳 조작 값 계산
            answer += Math.min(name.charAt(i)-'A','Z'-name.charAt(i)+1);
           
            //최소 이동 값 계산 
            int next = i+1;
            while(next<len&&name.charAt(next)=='A') next++;
          
            min_move = Math.min(min_move,i+len-next+i);
           
        }
        
        answer += min_move;
        
        return answer;
    }
}

왼->오 로 쭉 가는 경우 말고 돌아가는 경우의 기준을 어떻게 잡을 지 몰라서 못 푼 문제.. 다른 블로그를 보고 참고해서 겨우 이해했음ㅠ

• 알고리즘

  min_move: 조이스틱을 움직여서 가질 수 있는 이동값의 최대.
  왼쪽에서 오른쪽으로 쭉 한번씩 거쳐서 이동할 경우가 최대이므로 len-1이 됨.
  for문을 돌면서 알파벳 조작 값과 최소 이동값을 계산해야 함.
  1. 알파벳 조작 값(상하이동)
  (알파벳 - A)(down) 과 (Z - 알파벳+1)(up) 값 중 최소값을 구하고 answer에 더함.
  2. 최소이동 값(좌우이동)
  현재 문자의 다음 문자가 A일 경우 next++
  최종적으로 next가 가르키는 값은 A를 지나, A가 아닌 문자의 위치.
  min_move값과 (i*2)+len-next값 중 최소값을 구하고 answer에 최종적으로 더함.

(i*2)+len-next ??
좌->우로 쭉가는게 아니라 왼쪽으로 이동해서 위치를 이동시키고(반대 방향) 키를 조작하는 경우.
len - next : 총 길이에서 현재 바로 다음에 연속된 A가 지나고 남은 문자 갯수
i : 오른쪽으로의 현재까지의 이동횟수
i*2 + len - next : 현재까지 왔다가 다시 돌아가서 남은 거 까지 가는 이동 횟수

사실 아직도 저 (i*2)+len-next 부분 생각을 오래해야하지만..!ㅠ
커뮤니티를 보니까 이 문제가 그리디인가 아닌가에 대해서 많이들 논쟁하던데
나는 사실 모르겠음..우하하...알고리즘 초보이기때문에...~~ 노력하즈아

참고

조이스틱