Programmers 42860 조이스틱

16 Mar 2021 in Algorithm

문제 링크 : https://programmers.co.kr/learn/courses/30/lessons/42860

나의 풀이

조이스틱은 커서 이동과 문자 변경 두 가지 행동을 할 수 있다.
커서를 이동을 최소 이동으로 만들기 위해서는 좌측으로 가는 경우와 우측으로 가는 경우 중 더 작은 값을 선택해야한다.
마찬가지로 문자 변경을 최소화하기 위해서는 위로 조작하는 경우와 아래로 조작하는 경우 중 더 작은 값을 선택해야한다.

풀이 코드 : 42860 조이스틱

#include <string>
#include <vector>

using namespace std;



int move_(int start, int end, int size){
    int res;
    if(start <= end){
        res = end - start;
        if(res > size - end + start) res = size - end + start;
    }
    else{
        res = start - end;
        if(res > size - start + end) res = size - start + end;
    }
    return res;
}

int change(char target){
    int res = 'Z'-target+1;
    if(res > target - 'A') res = target - 'A';
    return res;
}

int find_next(int curr, vector<int> visit){
    int idx = -1;
    int len = visit.size();
    for(int i=0;i<visit.size();i++){
        if(visit[i] == 1) continue;
        int l = move_(curr, i, visit.size());
        if(len > l){
            len = l;
            idx = i;
        }
    }
    return idx;
}

int solution(string name) {
    int answer = 0;
    int curr = 0;
    vector<int> visit;
    visit.resize(name.size());
    for(int i=0;i<name.size();i++){
        if(name[i] == 'A') visit[i] = 1;
    }
    while(true){
        int next = find_next(curr, visit);
        if(next == -1) break;
        answer += move_(curr, next, name.size());
        answer += change(name[next]);
        visit[next] = 1;
        curr = next;
    }
    return answer;
}

채점결과