Programmers - 조이스틱 with JAVA (+)

문제

처음에 "AAAA" 처럼 A로만 이루어진 문자열이 주어진다.

그리고 만들려고 하는 문자열이 주어진다 예를 들어, "JJJJAAAN"이라고 하자.

시작은 인덱스 0에서 시작하는데 이동 횟수와 A를 J나 N으로 바꾸는 변경 횟수의 합의 최소값을 구하는 문제이다.

 

 

 

아이디어 & 로직

우선, A를 다른 문자로 바꾸는 변경을 위한 횟수는 정해져있다.

다만, A에서 -1을 하면 Z이기에 해당 만들려는 글자가 Z와 가까운지 A와 가까운지 확인하면 된다.

-> Math.min( 글자 - 'A' , 'Z' -글자 + 1)

 

이동 횟수는 항상 인덱스는 0에서 시작한다.

모든 인덱스에 대해서 경우의 수를 구하고 최소값을 구하면 된다.

예를 들어, 인덱스가 0 1 2 3 4 5 가 있다고 가정하고

3의 대한 경우의 수를 본다고 가정했을 떄, 

• 초기 오른쪽 이동 : "0에서 3까지 이동, 3에서 0까지 이동, 0에서 4까지 이동" 이 작은지
• 초기 왼쪽이동 : "0에서 4까지 이동, 4에서 0까지 이동, 0에서 3까지 이동" 이 작은지 비교한다.

 

하지만 만약 인덱스 4가 A라고 가정하자 그럼 굳이 A를 방문할 필요는 없다.

따라서 변경된 이동 경로는 다음과 같다.

• 초기 오른쪽 이동 : "0에서 3까지 이동, 3에서 0까지 이동, 0에서 5까지 이동" 이 작은지
• 초기 왼쪽이동 : "0에서 5까지 이동, 5에서 0까지 이동, 0에서 3까지 이동" 이 작은지 비교한다.

 

 

1. 모든 인덱스에 대한 경우의 수를 확인한다.

2. 문자 변경을 횟수는 고정이기에 그냥 더한다.

3. 해당 인덱스의 오른쪽에 'A'가 아닌 인덱스를 찾는다.

4. 이 후, 위에서 얘기한 경우를 비교해가며 움직임의 최소를 찾는다.

 

 

코드

class Solution {
    public int solution(String name) {
        int change = 0;
        int length = name.length();
        int move = length - 1;
        for(int i=0; i<length; i++){
            change += Math.min(name.charAt(i)-'A', 'Z'-name.charAt(i)+1);
            int index = i+1;
            while(index < length && name.charAt(index) == 'A'){
                index += 1;
            }
            move = Math.min(move, i * 2 + length - index);
            move = Math.min(move, (length - index) * 2 + i);
        }
        return change+move;
    }
}




class Solution {
    public int solution(String name) {
        int answer = 0;
        for(char now : name.toCharArray()){
            answer += Math.min((int)now-65, 90-(int)now+1);
        }
        int move = name.length()-1;
        for(int i=1; i<name.length(); i++){
            int right = 0;
            int left = 0;
            for(int j=i; j>=1; j--){
                if(name.charAt(j) != 'A'){
                    break;
                }
                right += 1;
            }
            for(int j=i+1; j<name.length(); j++){
                if(name.charAt(j) != 'A'){
                    break;
                }
                left += 1;
            }
            move = Math.min(move, 2*(i-right) + name.length()-1-i-left);
            move = Math.min(move, i-right + 2*(name.length()-1-i-left));
        }
        answer += move;
        return answer;
    }
}