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

문제 링크

 

풀이

마냥 쉬운 문제는 아닌 것 같습니다. 조이스틱의 위아래 조작의 최소 횟수를 찾는 건 쉽습니다. A->Z 방향, Z->A 방향으로의 조작 중 더 작은 값을 취하면 됩니다. 문제는 좌우 조작입니다. 몇 번 직접 사례를 찾아가면서 규칙을 찾아야 합니다.

 

ABABAAA의 경우를 보면 오른쪽으로 세 번만 움직이면 됩니다. 이것이 최소 횟수입니다. AABAAAAAB의 경우에는 먼저 왼쪽으로 한 번 갔다가 오른쪽으로 세 번 움직이는 게 최소 횟수입니다. ABAAAAABA의 경우는 일단 오른쪽으로 한 번 갔다가 왼쪽으로 세 번 가는 방법이 최소 횟수입니다. 이 세 가지의 경우 중 가장 작은 값을 구하면 되는 것입니다.

 

여기서 한 가지 공식을 만들 수 있습니다. 원점 기준 A가 아닌 위치를 찾고 나서, 다음 A가 아닌 인덱스를 갈 때 다시 원점으로 돌아가서 왼쪽으로 이동하는 경우를 2a + b로 표현할 수 있습니다. 왼쪽으로 먼저 이동했다가 돌아오는 건 2b + a로 표현할 수 있습니다. 즉 min(2a + b, 2b + a)인 것이죠. 이걸 조금 더 줄이면 a + b + min(a + b)가 됩니다.

 

코드

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

int get_up_down(char c)
{
    return c - 'A' < 'Z' - c + 1 ? c - 'A' : 'Z' - c + 1;
}

int solution(string name) 
{
    int answer = 0;
    int min_val = name.find_last_not_of('A');
    int size = name.size();
    for (int i = 0; i < size; ++i)
    {
        auto c = name[i];
        if ('A' == c) continue;
        else
        {
            answer += get_up_down(c);
            int next_idx = i;
            while ('A' == name[++next_idx]){}
            int m = i + size - next_idx + min(i, size - next_idx);
            min_val = min(min_val, m);
        }
    }
    return answer + min_val;
}