[프로그래머스] 조이스틱(Lv2, Greedy, 사고력, Java)

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

코딩테스트 연습 - 조이스틱

 

 

## 접근방법

---

조이스틱을 이용해서, 최소의 조이스틱 조작 횟수로 원하는 문자열을 만들어야 한다. 우선, 특정 위치에서 A에서부터 특정 문자를 만드는 것은, 위 혹은 아래로 이동하면 만들 수 있다.

 

 

 

위 방향으로만 이동하거나 아래 방향으로만 이동해야 최소로 문자를 만들 수 있다. 두 방향중에 작은 이동횟수를 선택해서 만들어주면 된다.

 

 

 

핵심은, 어떤 순서로 문자들을 방문할지 결정해야 한다.

 

 

 

최소 이동으로 모든 문자들을 만들기 위해서는, 현재 위치에서 원하는 문자열과 문자가 다른 가장 가까운 문자로 이동해야 한다. 이 방식으로 전역적 최적해를 구할 수 있다. 하지만 어떻게, 이 방식이 전역적 최적해를 구할 수 있는지에 대해서는 의문이 있다.

 

 

 

어떤 A가 아닌 문자의 입장에서 생각해보자, 이 문자의 입장에서 A가 아닌 가장 가까운 문자에서 방문해주면 최소 이동으로 방문되어진 것이다. 

 

 

 

모든 문자의 입장에서도, 가장 가까운 문자에서 방문해주면 최소 이동으로 방문이 된다. 따라서, 지역적 최적해가 전역적 최적해가 된다고 생각할 수 있다. 정확한 증명은 생각나지 않으므로 직관적으로 증명을 유도했다.

 

 

 

## 해설코드

---

class Solution {
    int getOrder(char c){
        return c - 'A';    
    }
    
    public int solution(String name) {
        int answer = 0;
        char[] cArr = new char[name.length()];
        for(int i = 0; i < cArr.length; i++) cArr[i] = 'A';
        int cur = 0;
        
        while(true){
            int minDis = name.length();
            int minIdx = -1;
            for(int i = 0; i < name.length(); i++){
                if(cArr[i] == name.charAt(i)) continue;
                
                int dis = Math.min(Math.abs(cur - i), name.length() - Math.abs(cur - i));
                if(dis < minDis){
                    minDis = dis;
                    minIdx = i;
                }
            }
            
            if(minIdx == -1)
                break;
            
            answer += minDis;
            int move1 = getOrder(name.charAt(minIdx)) - getOrder('A');
            int move2 = getOrder('Z') - getOrder(name.charAt(minIdx)) + 1;
            answer += Math.min(move1, move2);
            cArr[minIdx] = name.charAt(minIdx);
            cur = minIdx;
        }
        
        return answer;
    }
}