프로그래머스 Lv2 조이스틱 문제

• 프로래머스 Lv2 조이스틱 문제
  • 문제를 읽고 난 후의 분석
    • 조이스틱(4방향)으로 알파벳 이름 완성하기
    • 초기화 상태는 세글자면 'AAA', 네글자면 'AAAA'
    • name이 주어질 때 이름에 대하려 조작횟수의 최솟값 구하기가 목표
    • 최솟값? 최단거리? 를 구하기 위해 뭘 써야하나
    • 일단 조이스틱은 dx, dy를 활용한 방법같고
    • 범위 초과 시 처리는 있고
    • 뭔가 알파벳을 X 축, 글자위치를 Y로 본다면 이건 DFS 계열 같다
  • 해당 문제의 난이도 상승 원인
  • 해당 문제를 해결한 방법
  • 해당 문제를 해결였던 과정
    • 처음엔 BFS로 생각하고 BFS에 필요한 기본 재로코드를 타이핑하고 있었는데 문득 같은 단어를 치려고 해도앞으로 전진하면서 찾는 것보다 뒤로 후진하면서 찾는경우가 더 빠를 수 있다고 생각하여 BFS 가 아닌 , 이분 탐색? 에 가까운 경우로 보인거 같다
    • 그래서 알파벳 A, Z 를 기준으로 각각 0, 25로 정하고
    • {대상문자 - A, Z - 대상문자 + 1}식을 사용해 알파벳 이동에 대한 최소거리를 계산해냈으나 테스트케이스를 실행하니 조금씩 값이 다른것을 확인
    • 그래서 놓친 것이 있나 문제 지문을 다시 살펴보니 y축 또한 이와 비슷하게 처리해야 함을 인지
    • y구간 중 가장 긴 연속된 A 구간이 있다면 그것을 피하는게 최소 거리라고 생각되어 매 순환마다 다음 인덱스가 A 구간인지 확인하며 계산 후 정->역, 역->정 길이를 구한 다음 둘 중 최소값을 구함 그리고 추가로 문자열 길이 - 1 과 비교하여 최솟값을 구해서 갱신시킴
  • 문제의 핵심
    • 해당 문제가 좌우 이동이라는 특성을 이해해야함
      • continue는 건너뛰기지 방문 자체는 해버림
    • 가장 긴 A문자열을 체크해야하므로 정->역, 역-정 전체 길이를 구하고 최솟값을 판단

    • //전체 ------------------------------
      //기준 ---------|~~~~~|..............
      //다음 ---------------|++++++++++|...  
      // 정방향 과 역방향 은 어차피 NL -1 길이를 가지므로 묶임  
      // 정방향 + 역방향  
      // ((i * 2) + (전체 - 다음))
      // 역방향 + 정방향  
      // (((전체 - 다음) * 2) + i)

import java.util.ArrayList;
import java.util.List;

public class Lv2JoyStick {
    public static void main(String[] args){
        String name = "JEROEN";

        System.out.println(solution(name));
    }

    public static int solution(String name) {
        final int START = 'A'; // 65번이다
        final int END = 'Z'; // 90번이다
        final int NL = name.length(); // 문자열 마지막 인덱스

        //전체 ------------------------------
        //다음 ---------------|++++++++++|
        //기준 ---------|~~~~~|

        // 정방향 과 역방향 은 어차피 NL -1 길이를 가지므로 묶임
        // 정방향 + 역방향
        // ((i * 2) + (전체 - 다음)) % 전체
        // 역방향 + 정방향
        // (((전체 - 다음) * 2) + i) % 전체

        int x = 0;
        int y = NL - 1;
        for(int i = 0; i < NL; i++){
            int[] alpahDistArr = {name.charAt(i) - START, END - name.charAt(i) + 1};
            x += Math.min(alpahDistArr[0], alpahDistArr[1]);

            // 0은 초기 위치므로 계산에서 제외됨
            // next는 'A'의 마지막을 나타내는게 아니라 'A'가 아닌 다음 요소 인덱스
            int next = i + 1;
            while(next < NL && name.charAt(next) == 'A') next++;

            // 배열 내 각각의 수식은 정->역, 역->정에 대한 전체 이동길이를 나타내며
            // 연속된 A 구간 중 가장 긴 구간이 있을 때 짧아지는 것으로 생각된다
            // 그러므로 매 순환마다 최솟값을 체크하며 갱신해야한다.

            int[] cursorDistArr = {(i * 2) + (NL - next), (NL - next) * 2 + i};
            int compareVal = Math.min(cursorDistArr[0], cursorDistArr[1]);
            y = Math.min(y, compareVal);

            System.out.println("x :" + alpahDistArr[0] + ", " + alpahDistArr[1]);
            System.out.println("y :" + y);
            System.out.println("----------------------------");
        }
        return x + y;
    }
}