[프로그래머스/C++] 조이스틱 : Greedy

문제

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

풀이

이전 알파벳 or 다음 알파벳 / 다음 커서 or 마지막 커서
뭐가 최적의 해인지 매번 비교해나가는 전형적인 greedy 문제!

(아예 접근 자체를 어떻게 해야할지 모르겠어서 다른 사람들의 코드를 참고했는데 조이스틱이 중간에 방향을 바꾸는 경우를 고려하지 않아 애 먹었다 ,,)

반례) ABABAAAAABA

코드

#include <string>

using namespace std;

int solution(string name) {
    int answer = 0;
    int n = name.length();
    int turn = n-1;
    
    for(int i=0; i<n; i++) {
        if(name[i] - 'A' < 14) {
            answer += name[i] - 'A';
        }
        else {
            answer += 'Z' - name[i] + 1;
        }
        
        int index = i+1;
        while(index < n && name[index] == 'A') {
            index++;
        }
        
        int a = i;
        int b = n - index;
        turn  = min(turn, min(2*a+b, a+2*b));
    }
    
    answer += turn;
    return answer;
}