[알고리즘 C++] 조이스틱

오늘의 문제

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

조이스틱

나의 풀이

#include <string>
#include <vector>
#include <stdlib.h>

using namespace std;

int solution(string name) {
    int answer = 0;
    int size = name.size();
    
    vector<int> path;
    for(int i=0;i<size;i++){
        answer += min(name[i]-'A' , 'Z'- name[i]+1);
        if(name[i] != 'A' && i != 0)
            path.push_back(i);
    }
    
    int cur = 0;
    while(path.size() != 0){
        int minN = size+1;
        int minIdx = 0;
        for(int i=path.size()-1;i>=0;i--){
            int inc = abs(path[i] - cur);
            int dec = size - inc;
            minN = min(minN, min(inc, dec));
            if(minN == min(inc, dec))
                minIdx = i;
        }
        answer += minN;
        cur = path[minIdx];
        path.erase(path.begin()+ minIdx, path.begin()+ minIdx+1);
    }

    return answer;
}

모범 답안

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

using namespace std;

int LUT[] = { 0,1,2,3,4,5,6,7,8,9,10,11,12,13,12,11,10,9,8,7,6,5,4,3,2,1 };

int solution(string name) {
    int answer = 0;
    for (auto ch : name)
        answer += LUT[ch - 'A'];
    int len = name.length();
    int left_right = len - 1;
    for (int i = 0; i < len; ++i) {
        int next_i = i + 1;
        while (next_i < len && name[next_i] == 'A')
            next_i++;
        left_right = min(left_right, i + len - next_i + min(i, len - next_i));
    }
    answer += left_right;
    return answer;
}

배울 점

• LUT을 여기서 보다니 ㅋㅋㅋㅋㅋ 굉장하다
• 조금 복잡하게 또 생각한 것 같다. 단순하게 보자