[프로그래머스 알고리즘 고득점 Kit][그리디][Java] 조이스틱

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

프로그래머스

 

 

1. 각 글자의 위 아래를 먼저 구한다. -> 이건 위나 아래를 눌러서 비교함

2.  좌우 움직임 최소를 구한다.

 1) A구간을 최대한 피하는게 이득

 2) A구간이 2개이상이라면 구간 사이 처리해야할 글자가 생기기에 지나가야할 A구간은 무조건 생김
 3) 그러면 최소 하나의 A구간은 피해도 됨
 4) 피하지 않고 그냥 직진하는게 이득일 수도 있음
 5) 직진하는 값과 피하는 것을 비교후 최소값을 구함
 6) 피하는 것은 시작점을 기준으로 오른쪽으로 갔다가 왼쪽으로 돌아가는 경우
 7) 왼쪽으로 갔다가 오른쪽으로 돌아가는 경우가 있음
 8) A구간을 구하려고 보니 전체 문자열이 20이기에 그냥 모든 인덱스에 대해서 멈출 곳(A구간의 끝)만 찾아서 비교함

 

import java.util.*;

class Solution {
    public int solution(String name) {
        int answer = 0;
        int len = name.length();
        for(int i=0; i<len; i++) {
            char c = name.charAt(i);
            int cnt = Math.min(c - 'A', 26 - (c - 'A'));
            answer += cnt;
        }
        
        //그냥 오른쪽으로만 가거나
        int min = len - 1;
        //하나의 A구간을 피해가거나 -> A구간이 2개 이상이라면 구간 사이 처리해야할 이름이 있기에 하나 이상은 지날 수 밖에 없음
        //그래서 하나의 구간만 피하고 나머지는 지나는 경우 -> 이 말은 돌아가야하는 경우 -> 오른쪽으로 갔다가 왼쪽으로 가는 경우 또는 왼쪽으로 갔다가 오른쪽으로 가는 경우
        //i 는 내가 멈출 곳, cursor 는 A구간의 끝이라 멈출 곳

        // -> i를 0에서 len-1까지 다 보는 이유? -> 사실 모든 A구간의 시작과 끝을 찾아서 그 값으로 비교하는 게 맞지만 
        //길이가 짧기 때문에 그냥 모든 인덱스에 대해서 멈출 A구간(cursor)만 찾아서 값 비교.
        for(int i=0; i<len; i++) {
            int cursor = i+1;
            
            //A 구간의 끝. 멈출 곳 찾기
            while(cursor < len && name.charAt(cursor) == 'A') {
                cursor += 1;
            }
            
            int rightFirst = i * 2 + len - cursor; 
            // 0----->i
            // 0<-----i
            //         AAAAAA cursor<----len
            int leftFirst = (len - cursor) * 2 + i;
            //         AAAAAAcursor<-----len
            //         AAAAAAcursor----->len
            // 0----->i
            
            min = Math.min(min, rightFirst);
            min = Math.min(min, leftFirst);
        } 
        answer += min;
        
        return answer;
    }
   
   
}