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

조이스틱

문제 링크

조이스틱

분석

'A'에서 원하는 문자로 변경하는 데 필요한 최소 조작 수를 계산해야 합니다.
커서를 좌우로 이동하여 모든 문자를 변경하는 데 필요한 최소 이동 횟수를 계산해야 합니다.
결과적으로 문자를 변경하는데의 최소 조작수와 문자를 이동하는 최소 횟수를 더해서 반환해야합니다.

풀이

#include <string>
#include <algorithm>

using namespace std;

int solution(string name) {
    int answer = 0;
    int strLength = name.length();
    // 조이 스틱이 한 방향으로 쭉 이동하는 경우를 기본 값으로 사용
    int moveCount = strLength;

    for (int i = 0; i < strLength; ++i)
    {
        char c = name[i];
        answer += min(c - 'A', 'Z' - c + 1);

        // i기준 오른쪽으로 'A'가 아닌 첫 번째 문자의 위치를 구한다.
        int next = i + 1;
        while (next < strLength && name[next] == 'A')
        {
            ++next;
        }

        // i로부터 'A'가 아닌 문자까지의 거리
        int targetDistance = strLength - next;

        // 왼쪽에서 오른쪽으로 이동하는 최소 이동 횟수
        moveCount = min(moveCount, i * 2 + targetDistance);
        // 오른쪽에서 왼쪽으로 이동하는 최소 이동 횟수
        moveCount = min(moveCount, targetDistance * 2 + i);
    }

    // 구한 최소 이동 횟수를 더한다.
    answer += moveCount;

    return answer;
}

조이스틱이 한 방향으로 쭉 이동하는 경우에는 왼쪽, 오른쪽 상관 없이 name의 크기만큼 이동하기 때문에 크기를 기본 값으로 사용합니다.

min(moveCount, i * 2 + targetDistance) 이 코드의 i * 2는 오른쪽으로 i만큼 이동, 왼쪽으로 i만큼 이동한 것을 의미합니다.
여기에 targetDistance를 더한다면 이후에 바꾸기 위한 알파벳의 위치로 이동하는 횟수가 추가됩니다.

min(moveCount, targetDistance * 2 + i) 이 코드의 targetDistance * 2는 왼쪽으로 targetDistance이동하고, 오른쪽으로 targetDistance만큼 이동한 것을 의미합니다.
여기에 i를 더한다면 이후에 바꾸기 위한 알파벳의 위치로 이동하는 횟수가 추가됩니다.

성능 요약

시간 복잡도는 $O(n)$입니다.

• name을 순회하는 반복문 $O(n)$
• i기준 오른쪽으로 ‘A’가 아닌 첫 번째 문자의 위치를 구하는 반복문 $O(n)$
• $O(n) + O(n)$

공간 복잡도는 고정된 크기의 상수 공간을 사용하기 때문에 $O(1)$입니다.

테스트 성능

테스트 1 〉 통과 (0.01ms, 4.2MB)
테스트 2 〉 통과 (0.01ms, 4.15MB)
테스트 3 〉 통과 (0.01ms, 4.27MB)
테스트 4 〉 통과 (0.01ms, 4.16MB)
테스트 5 〉 통과 (0.01ms, 4.21MB)
테스트 6 〉 통과 (0.01ms, 4.15MB)
테스트 7 〉 통과 (0.01ms, 4.13MB)
테스트 8 〉 통과 (0.01ms, 4.2MB)
테스트 9 〉 통과 (0.01ms, 3.63MB)
테스트 10 〉 통과 (0.01ms, 3.65MB)
테스트 11 〉 통과 (0.01ms, 4.27MB)
테스트 12 〉 통과 (0.01ms, 4.2MB)
테스트 13 〉 통과 (0.01ms, 4.13MB)
테스트 14 〉 통과 (0.01ms, 4.01MB)
테스트 15 〉 통과 (0.01ms, 3.68MB)
테스트 16 〉 통과 (0.01ms, 4.14MB)
테스트 17 〉 통과 (0.01ms, 4.11MB)
테스트 18 〉 통과 (0.01ms, 4.2MB)
테스트 19 〉 통과 (0.01ms, 4.16MB)
테스트 20 〉 통과 (0.01ms, 3.64MB)
테스트 21 〉 통과 (0.01ms, 4.18MB)
테스트 22 〉 통과 (0.01ms, 4.21MB)
테스트 23 〉 통과 (0.01ms, 4.01MB)
테스트 24 〉 통과 (0.01ms, 4.21MB)
테스트 25 〉 통과 (0.01ms, 4.2MB)
테스트 26 〉 통과 (0.01ms, 4.14MB)
테스트 27 〉 통과 (0.01ms, 3.67MB)