[프로그래머스/Level 2] 조이스틱 (C++)

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

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

굉장히 어려웠던 그리디 유형 문제

한방향으로만 진행되는게 최소값이 아닐 수 있다. 따라서 왼쪽, 오른쪽으로 진행을 각각 해보고, 두개의 값중 최소값을 구하는 과정을 반복해야한다.

반례 : BBBAAAB -> 9

 

#include <string>
using namespace std;

int solution(string name) {
    int answer = 0;
    string tmp = "";
    
    // 초기 문자열 모두 A로 초기화
    for(int i = 0; i < name.size(); i++) {
        tmp.push_back('A');
    }
    int nowIdx = 0;
    while(1) {
        // 위, 아래 이동 중 최소값 구하기
        answer += min(name[nowIdx] - 'A', 'Z' - name[nowIdx] + 1); // A부터 시작하므로 +1
        tmp[nowIdx] = name[nowIdx];
        
        if(tmp == name) break; // 종료 조건
        
        // 왼쪽 이동
        int leftIdx = nowIdx, leftCnt = 0;
        while(tmp[leftIdx] == name[leftIdx]) {
            leftIdx--;
            leftCnt++;
            if(leftIdx < 0) leftIdx = name.size() - 1;
        }
        
        // 오른쪽 이동
        int rightIdx = nowIdx, rightCnt = 0;
        while(tmp[rightIdx] == name[rightIdx]) {
            rightIdx++;
            rightCnt++;
        }
        
        // 왼쪽 오른쪽 이동 중 최소값 구하기
        if(leftCnt < rightCnt) { // ????
            answer += leftCnt;
            nowIdx = leftIdx;
        } else {
            answer += rightCnt;
            nowIdx = rightIdx;
        }
    }
    return answer;
}