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

#include <string>
#include <algorithm>
using namespace std;

int solution(string name) {
    int answer = 0;
    int len = name.size();
    
    for (auto c : name) //다음 또는 이전 알파벳 
    {
        answer += min(c - 'A', 'Z' - c + 1);
    }

    // 기본 커서 이동 수
    int move = len - 1; 
    
    for (int i = 0; i < len; ++i) 
    {
        int next = i+1;
        
        // A찾기 
        while (next < len && name[next] == 'A') next++;

        move = min(move, i + i + (len - next)); //앞에 i만큼 탐사후 돌아와서 나머지 뒤 탐색
        move = min(move, i + (len - next) * 2); //뒤부터 탐사후 돌아와서 다시 i만큼 탐색
    }

    return answer + move;
}

 

먼저 알파벳 변경 같은 경우는 간단하게 현재 알파벳에 따라 앞에서부터 바꾸는게 빠른지, 뒤에서부터 바꾸는게 빠른지 선택한다.

 

이제 커서 이동 수이다.

기본적인 최대 커서 이동 수는 처음부터 오른쪽으로 쭉 이동하는 name.size()-1이다. (처음 칸 커서 이동 제외)

 

이제 A의 개수에 따라 이동 수가 달라진다.

A는 값을 바꾸지 않기에, A에 갈 필요가 없다.

따라서 A의 연속된 개수를 체크하고, 그 다음 변경 위치를 파악하여 이에 따라 커서 이동 최소값을 구하게 된다.

 

먼저 뒤에 A가 몰려있는 경우이다.

이런 경우는 앞에 i만큼 탐사후 다시 원점으로 돌아와서 뒤로 넘어가 나머지 값들을 탐색해준다.

BABBAAAAB 같은 문자열이 이에 해당한다.

(앞부분 B까지 탐색 -> 원점 복귀 -> 뒤 B로 이동) [원점 -> i -> 원점 -> 마지막 B]

 

다음으로 앞에 A가 몰려있는 경우이다.

이런 경우는 바로 뒤부터 탐사후 다시 원점으로 돌아와서 i만큼 탐색해준다.

AAAABAAB 같은 문자열이 이에 해당한다.

(바로 뒤 B 탐색 -> 원점 복귀 -> i만큼 이동(처음 B까지) [원점 -> 마지막 B -> 원점 -> i]

 

해당 방식을 모든 i위치에 대해서 탐색하며, 가능한 최소값을 구해 기존의 알파벳 변경 수와 합쳐 반환한다.