조이스틱

문제

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

코드

import java.util.*;

class Solution {
    public int solution(String name) {
        int answer = 20;

        int cursor = 0;

        int predicate[] = new int[4];
        for(int i=0; i<4; i++)
            predicate[i] = 20;

        String str = "";
        for(int i=0; i<name.length(); i++)
            str += 'A';

        for(int i=0; i<name.length(); i++){
            char cur_c = name.charAt(i);
            cursor += Math.min(cur_c - 'A', ('Z' - cur_c+1));
        }


        //1. 앞으로
        for(int i=0; i<name.length(); i++){
            if(name.charAt(i) != 'A')
                predicate[0] = i;
        }

        //2. 뒤로
        for(int i=0; i<name.length(); i++){
            if(name.charAt((name.length()-i)%name.length()) != 'A')
                predicate[1] = i;
        }

        //3. 앞으로 뒤로

        for(int i=0; i<name.length(); i++){
            int cur_val = i;
            for(int j=0; j<name.length(); j++){
                char char_c = name.charAt((name.length()+i-j)%name.length());
                if(char_c != 'A')
                    cur_val = i+j;
            }

            predicate[2] = Math.min(cur_val, predicate[2]);
        }


        //4. 뒤로 앞으로

        for(int i=0; i<name.length(); i++){
            int cur_val = i;
            for(int j=0; j<name.length(); j++){
                char char_c = name.charAt((name.length()-i+j)%name.length());
                if(char_c != 'A')
                    cur_val = i+j;
            }

            predicate[3] = Math.min(cur_val, predicate[3]);
        }

        for(int i=0; i<4; i++)
            answer = Math.min(answer, predicate[i]);

        return answer+cursor;
    }
}

피드백

• 이 문제는 문자를 바꿔야 되는 횟수 + 최소 이동수를 구하는 문제이다.
  • 문자 조작 횟수는 매우 쉬웠지만, 최소 이동수를 구하는 것은 시간이 꽤 걸렸다.
• 최소 이동수를 구하는 방법은 아래의 그림으로 설명이 가능하다.
  

  

  • 빨간 테두리를 바꿔야 되는 문자열이라고 하자
  • 해당 문제는 뒤로 이동해서 원형 큐처럼 이동할 수 있기에 앞 뒤 구분이 없다고 생각을 할 수 있다.
  • 그렇기 때문에 시작지점은 0 번지는 바꿔야되는 문자열의 어딘가에 위치 한다고 가정을 해 볼 수 있다.
  • 문자열을 위처럼 생각하게 된다면 우리가 생각해봐야 되는 가짓 수는 4가지이다.
  1. 오른쪽으로 직진
  2. 왼쪽으로 직진
  3. 오른쪽으로 갔다가 왼쪽으로 직진
  4. 왼쪽으로 갔다가 오른쪽으로 직진
  • 4 가짓수의 경우를 구해 최솟값을 산출하면 끝이다.