💻 조이스틱

분류 : Greedy (탐욕법)

사용 언어 : C++

문제 링크

🤔 문제 이해

문제 설명

조이스틱으로 알파벳 이름을 완성하세요. 맨 처음엔 A로만 이루어져 있습니다.
ex) 완성해야 하는 이름이 세 글자면 AAA, 네 글자면 AAAA

조이스틱을 각 방향으로 움직이면 아래와 같습니다.

▲ - 다음 알파벳
▼ - 이전 알파벳 (A에서 아래쪽으로 이동하면 Z로)
◀ - 커서를 왼쪽으로 이동 (첫 번째 위치에서 왼쪽으로 이동하면 마지막 문자에 커서)
▶ - 커서를 오른쪽으로 이동

예를 들어 아래의 방법으로 "JAZ"를 만들 수 있습니다.

- 첫 번째 위치에서 조이스틱을 위로 9번 조작하여 J를 완성합니다.
- 조이스틱을 왼쪽으로 1번 조작하여 커서를 마지막 문자 위치로 이동시킵니다.
- 마지막 위치에서 조이스틱을 아래로 1번 조작하여 Z를 완성합니다.
따라서 11번 이동시켜 "JAZ"를 만들 수 있고, 이때가 최소 이동입니다.

만들고자 하는 이름 name이 매개변수로 주어질 때, 이름에 대해 조이스틱 조작 횟수의 최솟값을 return 하도록 solution 함수를 만드세요.

제한 사항

• name은 알파벳 대문자로만 이루어져 있습니다.
• name의 길이는 1 이상 20 이하입니다.

해결 방안

초기 값에서 최단 횟수를 구하기 위해 왼쪽으로 가야하는지, 오른쪽으로 가야하는지, 각 알파벳당 위 혹은 아래로 몇번을 움직여야되는지 생각을 해야한다.

알파벳을 바꿀 땐 초기 A부터 시작하므로 알파벳을 바꾸는 횟수는 정해져 있을 것이다. 그럼 좌우로 움직이는 최단 횟수를 어떻게 구할 것인가가 포인트이다.

💡 문제 풀이

방법 1 )

알파벳을 최적으로 바꿔준 값을 저장한 map과 커서 이동 최적 값을 구하는 함수를 구현한다.

#include <string>
#include <vector>
#include <map>

using namespace std;

int left_distance(string correct_name, string change_name, int cursor_pos) {
    string change_str = change_name + change_name;
    string correct_str = correct_name + correct_name;
    int move = 0;

    for (int i = before_name.length() + cursor_pos; i >= 0; i--) {
        if (change_str[i] != correct_str[i]) return move;
        else move++;
    }

    return move;
}

int right_distance(string correct_name, string change_name, int cursor_pos) {
    string change_str = change_name + change_name;
    string correct_str = correct_name + correct_name;
    int move = 0;

    for (int i = cursor_pos; i <= correct_name.length() + cursor_pos; i++) {
        if (change_str[i] != correct_str[i]) return move;
        else move++;
    }

    return move;
}

int solution(string name) {
    int answer = 0;
    int cursor_pos = 0;
    string before_name(name.length(), 'A');
    map <char, int> change_alphabet_key = {
        {'A', 0}, {'B', 1}, {'C', 2}, {'D', 3}, {'E', 4}, {'F', 5}, {'G', 6}, {'H', 7}, {'I', 8}, {'J', 9}, {'K', 10},
        {'L', 11}, {'M', 12}, {'N', 13}, {'O', 12}, {'P', 11}, {'Q', 10}, {'R', 9}, {'S', 8}, {'T', 7}, {'U', 6},
        {'V', 5}, {'W', 4}, {'X', 3}, {'Y', 2}, {'Z', 1}
    };

    while (before_name != name) {
        int left_moving = left_distance(name, before_name, cursor_pos);
        int right_moving = right_distance(name, before_name, cursor_pos);

        if (left_moving < right_moving) {
            cursor_pos -= left_moving;
            if (cursor_pos < 0) cursor_pos += name.length();

            before_name[cursor_pos] = name[cursor_pos];
            answer += left_moving + change_alphabet_key[name[cursor_pos]];
        }
        else {
            cursor_pos += right_moving;
            if (cursor_pos > name.length()) cursor_pos -= name.length();

            before_name[cursor_pos] = name[cursor_pos];
            answer += right_moving + change_alphabet_key[name[cursor_pos]];
        }
    }

    return answer;
}

/*
정확성  테스트
    테스트 1 〉	통과 (0.01ms, 3.93MB)
    테스트 2 〉	통과 (0.01ms, 3.93MB)
    테스트 3 〉	통과 (0.02ms, 3.97MB)
    테스트 4 〉	통과 (0.01ms, 3.96MB)
    테스트 5 〉	통과 (0.02ms, 3.92MB)
    테스트 6 〉	통과 (0.01ms, 3.79MB)
    테스트 7 〉	통과 (0.02ms, 3.89MB)
    테스트 8 〉	통과 (0.01ms, 3.96MB)
    테스트 9 〉	통과 (0.01ms, 3.97MB)
    테스트 10 〉	통과 (0.01ms, 3.93MB)
    테스트 11 〉	통과 (0.01ms, 3.95MB)

채점 결과
    정확성: 100.0
    합계: 100.0 / 100.0
*/

시간 복잡도 : n * 2n

알파벳을 넣으면 최적의 값을 주는 change_alphabet_key와
다른 알파벳까지의 최단 거리를 구하는 left_distance, right_distance를 통하여 최적의 값을 구한다.

각 알파벳을 한번 바꿀때마다 최단 거리를 매번 다시 구하는 것이 포인트