[level 2] 조이스틱

문제 해설 및 주의사항

문제 설명

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

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

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

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

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

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

제한 사항

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

입출력 예

namereturn

"JEROEN"	56
"JAN"	23

 

풀이

1. 각 위치에서의 변형 (위 아래)

- 현재 위치의 가야할 값이 J 라면 A 에서 J 까지 몇번을 눌러야 하는지 알아야 한다. 'J' - 'A' 번 혹은 'Z' - 'J' + 1 번 중 작은 값을 선택한다.

2. 커서 이동 (왼쪽 오른쪽)

- 왼쪽 오른쪽 중 A 가 아닌 곳으로 이동한다. (그리디 알고리즘)

원문

3. 프로그래머스의 해설

조이스틱을 전체적으로 좌우로 움직이는 최소경로를 구하는것은,

어떤 특정 시점에서 (원점에서 출발하여 i번째 위치에 도착한 후) i번째 위치에서, i번째 위치에서부터 A가 아닌 (우측으로) next_i번째 떨어진 문자로 이동하는 과정에서 좌우로 움직이는 최소 이동횟수를 각 시점마다 탐색해가며 greedy하게 찾는 것이다.

(원점에서 출발하여) i번째에서 우측에 있는 A가 아닌 next_i번째 문자를 찾을 때 좌우 이동 총 횟수는

(i) 원점에서 i번째를 먼저 갔다가, 원점으로 되돌아가고 역주행하여 next_i번째로 최종도착한다.

(ii) 원점에서 역주행해서 next_i번째에 먼저 갔다가, 원점으로 정주행해서 되돌아가고 i번째에 도착한다

둘중 하나이다.

for문으로 각각의 i에서 그에 상응하는 next_i번째로 가는 길로의 좌우 최소경로를 탐색할때마다, 원점의 관점에서 시작해서 위의 2가지 방법 중 최소경로를 탐색하는 과정(좌우 이동횟수의 min을 찾는 과정. 이를 통해서 특정시점에서의 최소의 좌우이동횟수를 구할 수 있게 된다.)을 하게됨.

최종 left_right값은 어딘가의 i에서 그것의 next_i로 이동할때 최소 좌우 이동횟수의 경로인 (i)또는 (ii)중 하나의 모습일 것임.(즉, i또는 ii의 모습만 나옴. 최소경로니까 i했다가 ii했다가 i했다가 ii했다가 i하는 모습같은건 안나옴).

예를 들어서, [A 2개]C1[A 100개]C2[A 1억개]C3[A 2개] 라고 생각해보면, i=C2, next_i=C3 일때의, 그리고 위의 (ii)방식으로 이동했을때의 시점에서의 left_right값이 greedy하게 도출된 최소 좌우이동횟수의 값이다. 역주행해서 C3찍었다가 원점으로 돌아가고, [A1억개] 앞에있는 C2까지 정주행한 경로가 전반적으로 제일 저렴한 최종 left_right로 나온다. 그 외의 시점에서는 [A1억개]가 꼭 이동경로에 포함되버린다. 특정 시점이란 결국엔 i=C2, next_i=C3 처럼 중간에 A가 무지하게 많은 경우일 때임을 알 수있다. BAB의 경우도 좌우이동횟수 3, BB의 경우도 좌우이동횟수 2로 예외없이 잘 작동함.

풀이코드

#include <string>
#include <vector>

using namespace std;

int solution(string name) {
    int answer = 0;
    int n = name.size();
    int left_right = 123456789;
    int up_down = 0;
    for(int i = 0 ; i < name.size(); i++){
        // 위 아래 버튼 누르는 것 계산
        up_down += min(name[i] - 'A', ('Z' - name[i]) + 1);
        
        // 왼쪽 오른쪽 버튼 계산
        
        // 현재 값이 A 라면 생략
        if(name[i] == 'A') continue;
        
        int next_none_A = i + 1;
        while(next_none_A < n && name[next_none_A] == 'A'){
            next_none_A++;
        }
        int go_right = i;
        int go_left = n - next_none_A;
        
        left_right = min(left_right, go_right + go_left + min(go_right, go_left));
    }
 
    answer = up_down + left_right;
    return answer;
}

 

---

퇴고