[프로그래머스][LV2][C++]조이스틱

https://school.programmers.co.kr/learn/courses/30/lessons/42860

프로그래머스

 

그리디하게 접근하는 것이 중요하다고 생각했다.

1.알파벳 기준 절반이상이면 왼쪽으로 이동하는것이 이득, 아니라면 오른쪽으로 이동하는것이 이득

2.커서도 동일하게 길이의 절반이상이면 왼쪽으로 이동하는 것이 이득, 아니라면 오른쪽으로 이동

이렇게 생각하고 min으로 A부터 움직였을 때와 Z부터 움직였을 때의 최소값을 구한다.

그리고 커서를 움직이는 것을 생각해보면 

왼쪽으로 움직일때와 오른족으로 움직일때의 최솟값을 계산하면 된다. 

 

 

#include <string>
#include <algorithm>
using namespace std;
//알파벳 기준 절반이상이면 왼쪽으로 이동하는것이 이득, 아니라면 오른쪽으로 이동하는것이 이득
//커서도 동일하게 길이의 절반이상이면 왼쪽으로 이동하는 것이 이득, 아니라면 오른쪽으로 이동
int solution(string name) {
    int n = name.length();
    int answer = 0;
    
    // 각 알파벳을 바꾸는 데 필요한 조작 횟수를 합산
    for (int i = 0; i < n; ++i) {
        answer += min(name[i] - 'A', 'Z' - name[i] + 1);
    }
    
    // 커서 이동의 최소 조작 횟수를 구함
    int move = n - 1;
    for (int i = 0; i < n; ++i) {
        int next = i + 1;
        while (next < n && name[next] == 'A') {         //A건너뛰기 
            ++next;
        }
        move = min(move, i + n - next + min(i, n - next));      //왼쪽으로 갈때, 오른쪽으로 갈때 비교
    }
    
    return answer + move;
}