[Programmers/C++] 조이스틱

시간 복잡도

• for문이 최대 N번, while문은 전체적으로 N번 이기 때문에 $O(N)$ 입니다
• while문이 실행될 때마다 idx가 증가하면서 전체 문자열을 기준으로 한 번씩만 방분합니다.
• 따라서 while문이 여러 번 중첩되어 실행되지 않고 최대 N번만 실행됩니다

문제 접근법

• 임의의 문자 $x$에서 A가 되는 경우는 두 가지 입니다.
  1. 'A' -> '$x$': '$x$' - 'A'
  2. 'A' -> 'Z' -> '$x$': 'Z'-'$x$'+1
• 현재 문자의 위치($i$)에서 다음 A가 아닌 문자의 위치($idx$)를 구한 후 $i$와 $idx$를 찍는 두 가지의 경우에서 최솟값을 선택합니다.

코드

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

int solution(string name) {
    int answer = 0;
    int size = name.size();
    int turn = size - 1;
    for (int i = 0; i < size; i++) {
        answer += min(name[i] - 'A', 26 - (name[i] - 'A'));
        int idx = i + 1;
        while (idx < size && name[idx] == 'A')
            idx++;
        turn = min(turn, i + size - idx + min(i, size - idx));
    }
    answer += turn;
    return answer;
}