[프로그래머스 level2] 조이스틱

문제풀이

 

그리디 문제이다. 문제 lv2 문제였지만 나름 시간을 쓴 거 같다. 

마지막 테스트 케이스 때문에 코드를 전면 수정하였다.

한경로로 쭉 직진하는 거만 생각했는데 갔다 돌아오는 경우도 고려했어야되서

현재 코드처럼 수정하였다.

 

소스코드

#include <string>
#include <vector>
#include <algorithm>
#include <iostream>
using namespace std;
 
vector<int> counts;
int total_cnt = 0;
int solution(string name) {
    int result = 0;
    for (int i = 0; i < name.size(); i++) {
        int cnt = min(name[i] - 'A', 'Z' - name[i] + 1);
        counts.push_back(cnt);
        total_cnt += cnt;
    }
    int idx = 0;
    while (1) {
        
        result += counts[idx];
        //cout << idx <<","<<result<< endl;
        total_cnt -= counts[idx];
        counts[idx] = 0;
        if (total_cnt == 0)
            break;
        int left_cnt = 0;
        int right_cnt = 0;
        int left_idx = idx;
        int right_idx = idx;
        int n = name.size();
        while (counts[left_idx] <= 0) {
            left_cnt++;
            left_idx--;
            left_idx = (left_idx < 0) ? n - 1 : left_idx;
        }
        while (counts[right_idx]<=0) {
            right_cnt++;
            right_idx = (right_idx + 1) % n;
        }
        if (left_cnt < right_cnt) {
            result += left_cnt;
            idx = left_idx;
        }
        else {
            result += right_cnt;
            idx = right_idx;
        }
    }
    return result;
}
 
int main() {
    cout << solution("BBAABB") << endl;
}

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

프로그래머스