Programmers: 조이스틱

문제

• https://programmers.co.kr/learn/courses/30/lessons/42860
• 이건 그리디 라고는 하는데, 이게 그리디인가...? 브루트포스 아닌가..

문제 설명

• 처음 조이스틱에 주어지는 스트링은 A로 이루어져 있음
• 조이스틱 이동을 '최소화' 하는 형식의 문제
• 위/아래로 단어를 선택하고, 오른쪽-왼쪽으로 커서 이동
• 여튼 최소화가 가장 중요

기본 알고리즘

• while (joystick_string != input_string)
  • 현재 joystick_string 인덱스의 문자[=A]를 기준으로 가장 짧은 조이스틱 동작으로 input_string의 문자로 바꿀 수 있는 길이를 찾음
  • 그 수를 answer에 더함
  • 커서를 왼쪽으로 가거나, 오른쪽으로 갈 수가 있는데, 다음 joystick_string의 문자와 input_string 문자가 다른 인덱스를 찾음
    • 오른쪽, 왼쪽 둘다 찾은 뒤, 최소화 되는 값을 사용
  • 최소화 되는 값을 answer에 더해주고
  • 인덱스 업데이트

코드

#include <iostream>

using namespace std;

int get_smallest_move(char target) {
    if (target == 'A') {
        return 0;
    }
    int up_count = target - 'A';
    int down_count = 'Z' - target + 1;

    return min(up_count, down_count);
}

string create_a(int length) {
    string ret = "";
    for (int i = 0; i < length; i++) {
        ret += 'A';
    }
    return ret;
}

int solution(string name) {
    string creating = create_a(name.length());

    int target = 0;
    int answer = 0;

    while (creating != name) {
        answer += get_smallest_move(name[target]);
        // cout << movement << endl;
        creating.replace(target, 1, string(1, name[target]));
        if (creating == name) break;
        // cout << creating << endl;

        // Get Horizontal Moves
        int horizontal_right;
        int right_count = 0;
        if (target == name.length()-1) {
            right_count = 500;
        }
        for (int i = target; i < name.length(); i++) {
            if (name[i] != creating[i]) {
                horizontal_right = i;
                break;
            } else {
                right_count++;
            }
        }

        int horizontal_left;
        int i = target;
        int left_count = 0;
        while (true) {
            if (name[i] != creating[i]) {
                horizontal_left = left_count;
                break;
            } else {
                i--;
                left_count++;
                if (i < 0) {
                    i = name.length()-1;
                }
            }
        }

        answer += min(right_count, left_count);
        if (right_count > left_count) {
            target = i;
        } else if (right_count <= left_count) {
            target = horizontal_right;
        }
    }
    return answer;
}