조이스틱 (프로그래머스)

그리디 알고리즘 문제였다.

 

위, 아래로 조작하여 알파뱃을 바꾸는 것은 어렵지 않았지만, 개인적으로 왼쪽, 오른쪽  조작을 구하는 것이 좀 어려웠다.

 

 

 

예를 들어 JERAAN을 입력을 받으면 위아래 조작은 위와 같이 해야 최소한의 조작이 된다. 이 조작 횟수를 따로 담아 놓는다. 

 

이제 처음 위치부터 위, 아래로 조작한 횟수를 더해준다. 더해준 값은 0으로 갱신한다. (0인 경우는 그 위치에 알맞는 알파벳으로 조작을 완료했다는 뜻이다.)

 

그리고 현재 위치에서 왼쪽(초록색) 또는 오른쪽(주황색) 방향으로 갈 경우 0이 아닐 때까지의 거리를 측정한다. 이 거리를 측정하는 이유는 다음과 같다. 

 

그림과 같은 경우 오른쪽 방향으로 조작하면 6번을 해야 하지만, 왼쪽 방향으로 조작하면 3번만 해주면 된다. 즉 위아래 조작이 불필요한 A가 있는 위치는 최대한 거치지 않으면 왼쪽, 오른쪽 방향 조작을 최소한으로 만들어 줄 수 있다.

 

왼쪽, 오른쪽 둘 다 1만큼 이동하는 것으로 같으므로 오른쪽 조이스틱을 1번 조작하게 된다. 

 

이번에도 같은 과정을 반복한다. 오른쪽으로 1만큼, 왼쪽으로는 2만큼 조작해야 하므로 조작이 더 적은 오른쪽 조이스틱을 1번 조작하게 된다. 

 

왼쪽으로는 3만큼, 오른쪽으로는 3만큼으로 역시 똑같기 때문에 오른쪽 조이스틱을 3번 조작하게 된다. 

 

 

모든 값이 0이 되어 이름이 완성되었으므로 조작이 끝났다. 지금까지 기록한 조작 횟수를 더해주면 답이 된다. 9 + 1 + 4 + 1 + 9 + 3 + 13 = 40이 된다.

 

코드는 다음과 같다.

#include <string>
#include <vector>
#include <algorithm>

using namespace std;

// 컨테이너 모든 원소 값을 더해주는 함수
int sum (const vector<int> & v) {
    int result = 0;
    
    for (const auto & elem : v) {
        result += elem;
    }
    
    return result;
}

int solution(string name) {
    int n = name.size();
    vector<int> m (n);
    
    // 위 아래로 최소 조작 횟수를 집어 넣는다.
    for (int i=0; i<n; i++) {
        m[i] = min( name[i]-'A', 'Z'-name[i] + 1 );
    }
    
    int answer = 0;
    int where = 0;
    
    
    while (true) {
        // 위 아래중 최소의 방향으로 조작한다.
        answer += m[where];
        m[where] = 0;
        
        // 조작이 필요 없다면 반복문을 빠져나온다.
        if (sum(m) == 0) {
            break;
        }
        
        // 왼쪽 오른쪽으로 최소로 가기 위해 확인하는 값들
        int left = 0, right = 0;
        int leftIdx = where, rightIdx = where;
        
        // 왼쪽으로 0이 아닐때까지 이동해본다.
        while (m[leftIdx] <= 0) {
            left += 1;
            leftIdx = (leftIdx <= 0) ? (n - 1) : (leftIdx - 1);
        }
        
        // 오른쪽으로 0이 아닐때까지 이동해본다.
        while (m[rightIdx] <= 0) {
            right += 1;
            rightIdx = (rightIdx + 1) % n;
        }
        
        // 왼쪽 오른쪽 중 최소의 방향으로 조작한다.
        answer += (left < right) ? left : right;
        // 왼쪽 오른쪽 이동 횟수중 더 적은 횟수 방향으로 이동한다.
        where = (left < right) ? leftIdx : rightIdx;
    }
    
    return answer;
}