[프로그래머스 LV2] - 조이스틱(그리디) c++

문제

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

프로그래머스

접근방법

각 알파벳의 최소 조작 횟수를 계산하는 것은 어렵지 않았다.

 

하지만, 

좌우로 움직이는 횟수를 최소로 만드는 것이 어려웠다.

 

움직이는 순간마다.

좌우로 최소움직임 수를 계산하는 방법을 사용하니

해결 가능했다.

 

코드

#include <string>
#include <vector>
#include <algorithm>
#include <iostream>
using namespace std;

// A에서 시작해서 target 알파벳을 완성하는 데 필요한 최소 조작 횟수를 계산하는 함수
int minMoves(char target) {
    return min(target - 'A', 'Z' - target + 1);
}

int solution(string name) {
    int answer = 0;
    int n = name.size();
    
    int min_num = n-1;
    for (int i=0;i<name.size();i++) {
        answer += minMoves(name[i]); 
        
        int next = i + 1;
        while(next < name.size() && name[next] == 'A') next++;
        min_num = min(min_num, min(i * 2 + (n-next), (n-next) * 2 + i));
    }
    answer += min_num;
    
    
    return answer;
}

개선할 점

min_num = min(min_num, min(i * 2 + (n-next), (n-next) * 2 + i));

움직일 때마다 가장 짧은 거리를 계산.