알고리즘(C++) / 프로그래머스 level 2 : 조이스틱

level 2 : 조이스틱

https://programmers.co.kr/learn/courses/30/lessons/42860?language=cpp 

코딩테스트 연습 - 조이스틱

 

코드

//프로그래머스 조이스틱
#include <iostream>
#include <string>
#include <vector>
#include <algorithm>
#include <cmath>

using namespace std;

int solution(string name) {
    int answer = 0;
    int turn = name.size() - 1;
    int n = name.size();
    for (int i = 0; i < name.size(); i++) {
        if (name[i] - 'A' <= 13) {
            answer += (name[i] - 'A');
        }
        else {
            answer += 26 - (name[i] - 'A');
        }
        
        int next = i + 1; //다음 문자
        while (next < name.size() && name[next] == 'A')
            next++;
        turn = min(turn, i + n - next + min(i, n - next));

    }

    answer += turn;
    return answer;
}

int main() {
    string name = "JEROEN";
    cout << solution(name) << "\n";
    return 0;
}

 

설명

이번 문제는 조이스틱을 움직여 원하는 이름을 최소한의 움직임으로 만드는 것이다.

 

알파벳을 최소한으로 움직여 만들기 위해서는 B, C, D, E, F, G, H, I, J, K, L, M, N 13개의 알파벳은 ▲을 눌러 이동하고, 나머지 알파벳은 ▼을 눌러 이동한다. 이때 초기 알파벳은 A이므로 A는 움직이지 않아도 된다.

예) ▲을 9번 조작하여 만들 수 있다. 

 

각 위치의 이동을 최소한으로 움직여 만들어야 한다. 초기 알파벳은 A이다. 따라서 만들고자 하는 이름이 A라면 커서를 이미 A인 위치로 이동하지 않아도 된다.

예를 들어 JAN 같은 경우는 두 번째 글자가 A이기 때문에 첫 번째 알파벳을 J로 변경한 후 N으로 커서를 움직여 N으로 조작하여 두 번째 글자로 커서를 움직이지 않아도 된다.

여기서 생각해볼 경우가 있다.

ABAAAB 같은 경우는 ▶◀◀으로 움직여야 한다.

최솟값을 찾기 위해서는 왼쪽과 오른쪽을 둘 다 사용하여 움직여야 하는데 여기서 어떻게 하면 최소한의 움직임을 찾을 수 있을지 생각해보아야 한다.

    for (int i = 0; i < name.size(); i++) {
        int next = i + 1; //다음 문자
        while (next < name.size() && name[next] == 'A')
            next++;
        turn = min(turn, i + n - next + min(i, n - next));

    }

빨간색 화살표는 i 파란색 화살표는 next를 나타낸다.

위 코드를 다음과 같이 나타낼 수 있다.

여기서 빨간 화살표의 위치와 파란 화살표의 위치는 빨간 화살표에서 A가 아닌 다른 알파벳의 위치를  나타낸다. 

첫번째 커서에서 빨간색 화살표 위치까지 ▶ 움직인 횟수와 첫 번째 커서에서 파란색 화살표 위치까지 ◀ 움직인 횟수 중 작은 값을 선택하고 빨간 위치에서 파란 위치의 거리를 더해 준 값과 원래 turn 값을 비교하여 작은 값을 선택하는 것이 움직임의 최솟값이다.

 

 

고찰

알파벳을 움직이는 건 어렵지 않았지만 어떤 순서르 커서를 옮겨야 하는지가 관건이었다. 

커서를 최소한 옮겨 원하는 이름을 만들어야 하지만 쉽게 생각해내지 못했다.

결국 구글링하여 최소 이동을 알 수 있었다.

 

min() 함수를 사용할 때 name.size()를 사용하면 안 된다. min함수 안에는 int형 자료만 사용이 가능하고 name.size()의 반환형은 unsigned int 형으로 맞지 않으므로 int형으로 변환해준 후 사용이 가능하다. 

int n = name.size();