프로그래머스 - 탐욕법 ( Greedy ) - 조이스틱

 

 

---

 

---

 

[ 코드 보기 ]

 

import java.util.*;

class Solution {
    
    public int solution(String name) {
        
        // 문제 :
        // 조이스틱으로 알파벳 이름을 완성하세요. 맨 처음엔 A로만 이루어져 있습니다.
        // 만들고자 하는 이름 name이 매개변수로 주어질 때, 
        // 이름에 대해 조이스틱 조작 횟수의 최솟값을 return 하도록 solution 함수를 만드세요.
        
        int answer = 0;
        // + 변수 answer에는 조작횟수를 저장한다.
        
        int LR = name.length() -1;
        // + LR은 좌우로 움직일 수 있는 횟수의 최대치를 저장한다.
        
        for ( int i = 0; i < name.length(); i++ ){
            
            // =============================
            // + 1단계 : 위 / 아래 조작 비교
            // =============================
            
            char t = name.charAt(i);
            
            // + 영문자의 경우, 아스키 코드로 변환하면 65 - 90번에 해당한다.
            // + 그렇기에 아스키 코드 값 - 65를 하면 0 - 25까지의 범위를 가지게 된다.
            // + 위로 조작했을 때는 t - 65, 
            // + 아래로 조작할 경우에는 25 - ( t - 65 ) + 1를 해줘야 이동횟수를 구할 수 있다.
            
            answer += Math.min( t - 65, 25 - ( t - 65 ) + 1);
            // + Math.min을 통해서 최소값을 answer에 더하게 된다.
            
            // =============================
            // + 2단계 : 좌 / 우 조작 비교
            // =============================
            // + 연속된 A문자가 있을 경우 위 / 아래의 조작은 필요가 없기에,
            // + 좌측으로 움직이는게 이득인지, 우측으로 이동하는게 이득인지 파악해야 한다.
            // + 그렇기 위해 먼저 A의 마지막 위치가 어디인지 파악해야 한다.
            
            int index = i + 1;
            // + 마지막 A를 찾는 것이기에 인덱스번호 1번부터 찾으면 된다.
            
            while ( index < name.length() && name.charAt(index) == 'A' ) {
                
                index++;
                // + A가 나올때마다 +1을 해주어, A의 마지막 위치를 파악해 준다.
                
            } // while
            
            LR = Math.min(LR, i + (name.length() - index) + Math.min(i, name.length() - index));
            // + 그냥 LR의 경우에는 연속되는 A가 없어 모든 자리를 이동해야 되는 경우이다. ( 한쪽으로만 이동 )
            // + 후자의 경우에는 가다가 A를 만나 왼쪽으로 돌아가는 경우이다.
            // + 이 경우 이동횟수가 A를 만나기 전의 이동횟수 + 왼쪽으로 다시 돌아가서 이동하는 횟수로 구해야 한다.
            
        } // for       
        
        return answer + LR;
        
    } // solution
    
} // end class

---

 

[ 참고한 블로그 ]

 

https://hu-coding.tistory.com/m/121

[Java] 프로그래머스 Lv.2 > 조이스틱