[프로그래머스][JAVA] 조이스틱 (완전탐색/ 그리디...?)

알파벳을 바꾸는 부분은 어렵지 않다.. 중요한 부분은 좌우키를 어떤 식으로 움직여서 최소한으로 움직이느냐인데..

실패했다

 

Line:19가 너무나 중요함

import java.util.*;
 
class Solution {
    private static int answer;
    // private static List<Integer> noAindexList;
    
    public int solution(String name) {
        answer = 0;
 
        int len = name.length();
        int min = name.length()-1;
        
        for(int i=0; i<len; i++){
            addAlphabetNum(name, i);
            
            int next = i+1;
            while(next<len && name.charAt(next)=='A') next++;
            int ni = len-next;
            min = Math.min (min , Math.min(2*i+ni, i+2*ni));
        }
        answer+=min;
        // System.out.println(min);
 
        
        return answer;
    }
 
    
    private void addAlphabetNum(String name, int i){
        if(name.charAt(i)!='A'){
            answer += changeAlphabet(name, i);
        }
    }
    
    private int changeAlphabet(String name, int i){
        return Math.min(name.charAt(i)-'A', 26-(name.charAt(i)-'A'));
    }
}
 

 

 

 

대충 이런 그림인데 i의 범위가 0<= i < len이기 때문에

어떠한 AAA...AAA를 사이에두는

(이 A의 개수가 0인 경우도 포함 즉 A가 아닌 문자가 연속되는 것들도 ex)JEROEN

사이에 A의 공집합이 있다고 가정하는거임)

두 index인 i와 next의 모든 경우의 수를 다 찾아서 min값에 Math.min으로 비교할 수 있음

 

저렇게 구한 값중 2*i+ni가 더 작냐 i+2*ni가 더 작냐 비교 후 그 값은 min값의 후보군이 될 수 있음

2*i + ni의 의미 => 

0번 index에서 i번 index로 먼저 갔다 온 후에 next번 index로 가서 마무리 짓는다는 의미
조이스틱을 움직이기전 가장 처음의 index의 번호는 0번임
즉 i쪽으로 먼저 간 다음에(1*i) 다시  돌아와서(1*i) --> 총 2*i
0번 index에서 왼쪽으로 1번 꺽으면 len-1번 index임
그것을 활용해서 next까지의 최소 거리는 len-next로 ni라는 변수에 저장해줌

i + 2*ni의 의미 => 

이건 0번 index에서 i번 index로 먼저 갔다 오는 것이 아닌 next번 index를 먼저 갔다온다는 의미

                         

 

 

 

 

 

 

 

---

 

 

Line:18~19를 정확하게 이해해야함 이게 좌우이동 최소값을 찾는 공식임..

이거 다 이해하고도 설명하기가 힘든데

문제 처음 봤으면 절대로 나올 수 없을 공식임..ㅠ

댓글단거 퍼옴

앞으로 쭉가는 경우는 처음 초기화로 하드코딩합니다. min = length. 그것보다 작은 경우를 찾는 알고리즘이 min = Math.min(min, i + length - next + Math.min(i, length - next)); 입니다. i+length-next는 '바로옆의 a들을 제외한 다른 문자들의 길이 -1' 입니다. 예를 들면 AAABBBBBBBAA 는 I=2일 경우 next = 10, length는 12 이어서 4이됩니다. 즉, B를 건너지 않고 반대로 넘어가는 경우를 고려하는 것입니다. 여기서 문제는 우리의 시작점은 인덱스 0인것에 있습니다. 우리는 i까지 갔다가 되돌아가거나 처음부터 뒤로가서 length-next까지 갔다가 다시 돌아오는 경우를 생각해야합니다. 앞의 예에서는 i=2 두칸앞으로 갔다가 돌아오느냐, 처음부터 뒤로가서 length-next = 12 - 10 = 2를 고려해야하는 것입니다. 이 경우에는 두개가 같은 값이지만 다를 수 있어서 Math.min으로 방향을 선택해주는 것입니다. 위의 댓글이 정확하지 않아서 댓글답니다.

 

class Solution {
    public int solution(String name) {
        int answer = 0;
        
        char[] chr = name.toCharArray();
        
        int leftAndRight = name.length();
        
        for(int i=0; i<chr.length; i++){
            if(chr[i]!='A') {
                int a = (int)(chr[i]-'A');
                int b = 26-(int)(chr[i]-'A');
                int upAndDown = (a>b)? b:a;
                answer+=upAndDown;
            }
            int next = i+1;
            while(next<chr.length && chr[next]=='A') next++;
            leftAndRight = Math.min(leftAndRight,
                    i+(chr.length-next)+Math.min(i,chr.length-next));
            
        }
        
        answer+=leftAndRight;
        
    
        
        
        
        
       
        
        return answer;
    }
}

 

 

 

 

 

 

 

 

이게 그리디인데 이걸로 하면 틀림..

import java.util.*;
 
class Solution {
    private static int answer;
    private static List<Integer> noAindexList;
    
    public int solution(String name) {
        answer = 0;
        noAindexList = new ArrayList<>();
        int len = name.length();
        
        for(int i=0; i<name.length(); i++){
            addAlphabetNum(name, i);    
        }
        
        int currIdx = 0;
        while(!noAindexList.isEmpty()){
            noAindexList.forEach(i-> System.out.print(i+" "));
            
            int rightIdx = noAindexList.get(0);
            int leftIdx = noAindexList.get(noAindexList.size()-1);
            int rightShort = shortMoveNum(currIdx, rightIdx, len);
            int leftShort = shortMoveNum(currIdx, leftIdx, len);
            
            if(rightShort<=leftShort){
                // System.out.print(" right"+rightShort);
                currIdx = rightIdx;
                noAindexList.remove(0);
                answer+=rightShort;
            }
            else{
                // System.out.print(" left");
                currIdx = leftIdx;
                noAindexList.remove(noAindexList.size()-1);
                answer+=leftShort;
            }
            
            System.out.println();
        }
 
        
        return answer;
    }
    
    private int shortMoveNum(int a, int b, int len){
        int small = Math.min(a,b);
        int big = Math.max(a,b);
        return Math.min(big-small, len-big+small);
    }
    
    private void addAlphabetNum(String name, int i){
        if(name.charAt(i)!='A'){
            answer += changeAlphabet(name, i);
            noAindexList.add(i);
        }
    }
    
    private int changeAlphabet(String name, int i){
        return Math.min(name.charAt(i)-'A', 26-(name.charAt(i)-'A'));
    }
}