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

아직 풀지 못한 문제이다.

---

문제 설명

최소 횟수로 조이스틱을 움직여 name을 입력할 때, 그 횟수를 구하시오.

https://school.programmers.co.kr/learn/courses/30/lessons/42860

프로그래머스

 

입출력 예

"JEROEN" 56
"JAN" 23

 

풀이

원하는 알파벳으로 바꾸기 위해서 요구되는 이동 횟수는 언제나 일정하다 --> min(name[i] - 'A', 26 - (name[i] - 'A'));

 

그러므로 이 문제에선 좌우 이동횟수를 최소화하는 것이 핵심이다. --> 그리디 알고리즘을 이용하면 가능하다. 

 

그러나 그리디 알고리즘을 통해 해를 구하는 과정에서, 좌-우 이동의 가중치가 같다면, 어느 방향을 선택할 것인지에 대해서 잘 결정해야 하는데, 그걸 아직 하지 못했다. 예를 들어, BBAAAAABBB에서 기댓값은 10이지만, 이걸 좌-우 이동의 가중치로만 결정하면, 12가 나올 수도 있다.

 

코드

#include <vector>
#include <string>
#include <iostream>

using namespace std;

int solution(string name)
{
    int answer = 0;

    // 적어도 이 횟수만큼은 무조건 조이스틱을 움직여야 함
    for (int i = 0; i < name.length(); i++)
        answer += min(name[i] - 'A', 26 - (name[i] - 'A'));
    cout << "essential : " << answer << endl;

    // greedy
    int right_weight;
    int left_weight;
    int r_move_point;
    int l_move_point;
    int unvisited_right;
    int unvisited_left;
    int limit;
    vector<bool> is_visited;
    for (int i = 0; i < name.length(); i++)
        is_visited.push_back(false);
    int i = 0; // current position
    
    while (true)
    {
        is_visited[i] = true;
        unvisited_right = 0;
        unvisited_left = 0;

        // 오른쪽 진행
        limit = 0;
        for (int j = i; j < name.length();)
        {
            j++;
            limit++;
            if (limit >= name.length()) // 다른, A가 아닌 문자를 찾지 못함.
            {
                right_weight = -1;
                break;
            }
            if (j >= name.length())
            {
                j = 0;
            }
            if (name[j] != 'A' && is_visited[j] == false)
            {
                r_move_point = j;
                right_weight = limit;
                for (int k = i; k < name.length(); k++)
                {
                    if (name[k] != 'A' && !is_visited[k])
                        unvisited_right++;
                }
                break;
            }
        }

        // 왼쪽 진행
        limit = 0;
        for (int j = i; j >= 0;)
        {
            j--;
            limit++;
            if (limit >= name.length()) // 다른, A가 아닌 문자를 찾지 못함.
            {
                left_weight = -1;
                break;
            }
            if (j < 0)
            {
                j = name.length() - 1;
            }
            if (name[j] != 'A' && is_visited[j] == false)
            {
                l_move_point = j;
                left_weight = limit;
                for (int k = i; k >= 0; k--)
                {
                    if (name[k] != 'A' && !is_visited[k])
                        unvisited_left++;
                }
                break;
            }
        }

        // conclude
        cout << "current char : " << name[i] << " | left : " << left_weight << " | right : " << right_weight << endl;
        if (left_weight > right_weight)
        {
            cout << "RIGHT!!!" << endl;
            i = r_move_point;
            answer += right_weight;
        }
        else if (left_weight < right_weight)
        {
            cout << "LEFT!!!" << endl;
            i = l_move_point;
            answer += left_weight;
        }
        else // left_weight == right_weight
        {
            // 둘 다 -1인 경우 무조건 여기로 오게 되어있음
            if (right_weight == -1 && left_weight == -1) // 종료 조건
                break;
            else
            {
                if (unvisited_right > unvisited_left)
                {
                    cout << "NEUTRAL-RIGHT!!!" << endl;
                    // right
                    i = r_move_point;
                    answer += right_weight;
                }
                else
                {
                    cout << "NEUTRAL-LEFT!!!" << endl;
                    // left
                    i = l_move_point;
                    answer += left_weight;
                }
            }
        }
    }

    return answer;
}

int main(void)
{
    //string name = "JAN";
    //string name = "JEOREN";
    //string name = "AAZ";
    //string name = "BBAAAB";
    //string name = "ABAAAB";
    string name = "BBAAAAABBB"; // 황금 반례
    //string name = "BBBAAAAABBB";
    cout << solution(name);
}