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

문제 설명

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

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

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

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

- 첫 번째 위치에서 조이스틱을 위로 9번 조작하여 J를 완성합니다.
- 조이스틱을 왼쪽으로 1번 조작하여 커서를 마지막 문자 위치로 이동시킵니다.
- 마지막 위치에서 조이스틱을 아래로 1번 조작하여 Z를 완성합니다.

따라서 11번 이동시켜 “JAZ”를 만들 수 있고, 이때가 최소 이동입니다. 만들고자 하는 이름 name이 매개변수로 주어질 때, 이름에 대해 조이스틱 조작 횟수의 최솟값을 return 하도록 solution 함수를 만드세요.

제한사항

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

---

풀이

문제를 임의로 이해해버려서 헤맸다. 알파벳을 정하기 위해서 상하로 움직이는 횟수의 최솟값은 쉽게 구할 수 있었다. 하지만 좌우로 움직이는 과정에서 인덱스 0번에서 왼쪽으로 이동했을 때 마지막 문자로 커서가 이동한다는 조건을 보고, 마지막 인덱스에서 오른쪽으로 이동하면 첫 번째로 이동한다고 무의식적으로 생각해버렸다. 때문에 처음에 뒤로 이동했다가 앞으로 다시 오는 경우까지 생각하니, 이게 그리디인지에 대한 의문점이 들 정도로 생각한 방법에 대한 반례가 너무 많이 떠올랐다. 비록 그리디 문제이지만 이름이 20자 이하이므로 그냥 brute force로 풀려고 하는 찰나에 문제를 잘못 이해한 것을 깨달았다.
문제를 다시 이해한 후로는 매번 이동마다 앞으로 이동하는 것과 뒤로 돌아서 이동하는 것 중 최선을 고르는 형태의 그리디 방식을 통해서 문제를 풀었다. 이 방식을 쉽게 구현하기 위해서 방문해야하는 인덱스를 벡터로 저장해서 풀게 되었다.

코드

#include <string>
#include <vector>
#include <cmath>
#include <algorithm>

using namespace std;

int solution(string name) {
    int cnt = 0;
    vector<int> v;
    for(int i = 0; i < name.length(); ++i){
        if(name[i] != 'A') v.push_back(i);
        cnt += min(name[i] -'A','Z'- name[i] + 1);
    }
    for(int i = 0; i < v.size(); ++i){
        if(i == v.size() - 1){
            cnt += v[v.size()-1];
            break;
        }
        if(v[i]*2 + name.length() - v[i+1] < v[v.size()-1]){
            cnt += v[i]*2 + name.length() - v[i+1];
            break;
        }
    }
    return cnt;
}