[프로그래머스] Level2 - 조이스틱 (C++)

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

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

[풀이] Greedy

 

가장 효율적으로 알파벳을 변경하는 방법은 이동시 가장 가까운 곳으로 이동해서 변경해주는 것이다.

어차피 변경해야할 모든 알파벳을 방문해야 하기 때문이다.

 

어떤 알파벳을 방문할 때 <-,->를 이용하는 두가지 방법 중 min값이 이동거리이다.

 

#include <string>
#include <vector>
#include <iostream>
#include <cmath>
#include <algorithm>
using namespace std;
int solution(string name) {
    int answer = 0;
 
    string curName(name.size(), 'A');
    int cur = 0;
 
    while (name != curName) {
 
        int near = -1;
        int minDiff = 30;
        for (int i = 0; i < name.size(); i++) {
            if (name[i] != curName[i]) {
                int diff = abs(cur - i);
                diff = min(diff, (int)name.size() - diff);
                if (minDiff > diff) {
                    near = i;
                    minDiff = diff;
                }
            }
        }
        cur = near;
        curName[cur] = name[cur];
        answer += minDiff;
        
        int k = name[cur] - 'A';
        answer += min(26 - k, k);
 
        //cout << "cur : " << cur << ", minDiff : " << minDiff << ", k : " << k << ", len -k : " << 26-k << endl;
    }
 
    return answer;
}

https://github.com/has2/Algorithm/blob/master/programmers/level2/%EC%A1%B0%EC%9D%B4%EC%8A%A4%ED%8B%B1.cpp