1. 문제설명

조이스틱을 활용해 주어진 알파벳을 완성할 때 움직인 횟수 return
- 초기 모든 문자는 A로 설정되어 있다.

규칙

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

2. 입/출력

입력
- 만들고자 하는 이름 name
출력
- 이름에 대해 조이스틱 조작 횟수의 최솟값을 return

3. 문제 분류

Greedy, Simulation

4. 알고리즘 설계

혹시나 문제를 이해하지 못한 분들이 있을 거 같아 예시로 설명해보려고 한다!
AAA를 JAZ로 만들어보자
- 초기 상태는 AAA이다.
  - 글자수만큼 A로 되어있는 것
- A -> J
  - 뒤로 가는 것보다 앞으로 가면 더 적은 횟수로 이동 가능하며 이 때의 값은 9이다.
- J에서 A로 1칸 이동
- A -> A
  - 이미 완성되어 있으므로, 0이다.
- A에서 Z를 만들기 위한 칸으로 1칸 이동
- A -> Z
  - A에서 앞으로 Z까지 가는 것보다 뒤로 이동하면 1번의 이동으로 완성할 수 있다.
본인은 A에서 특정 알파벳까지 가는 경로를 배열로 지정해 사용했다.
- 즉 A -> Z라면 앞으로 가는 것과 뒤로 가는 비용을 비교하지 않고 그냥 cost[Z] = 1을 사용했다.
여기까진 쉬운데, 조이스틱을 움직이는 횟수가 관건이다.
- “ABABAAAAABA” 문자열에서, 4번째 B를 완성했고 뒤에서 2번째 B를 완성해야 한다.
- 앞으로 이동하는 것과 뒤로 이동하는 것 중 어떤 게 더 짧은지 계산할 수 있을까?
- 원점을 0번째, 현재 위치를 cur, 다음 이동하 위치를 nxt라고 해보자
  - 0 -> cur -> 0 -> nxt
  - 0 -> nxt -> 0 -> i
  - 0 -> cur가 a, 0 -> nxt가 b라고 하면 각각은 2a + b, a + 2b가 된다.
  - min(2a + b, 2b + a) == a + b + min(a, b)가 성립한다.
  - 이제 이걸 다시 원래의 값으로 되돌리면
    - cur + len - nxt + min(cur, len - nxt)
    - 여기서 len은 문자열의 길이가 된다.

5. 전체 코드

#include <bits/stdc++.h>
using namespace std;

int A[26];

int solution(string name) {
    int ans = 0;
    int len = name.size();
    int cmp = len - 1;
    
    // 거리 초기화
    for(int i=0; i<=13; i++) A[i] = i;
    for(int j=12, i=14; i<26; i++, j--) A[i] = j;
    
    for(int i=0; i<len; i++) {
        ans += A[name[i] - 'A'];
        
        int tmp = i + 1;
        while(tmp < len && name[tmp] == 'A') tmp++;
        cmp = min(cmp, i + len - tmp + min(i, len - tmp));
    }
    
    return ans + cmp;
}

6. 소감

문제를 읽자마자 그리디인 건 눈치채기 쉬웠다.
조이스틱 움직이는 횟수를 최소화 하는 게 관건이었다.
아이디어가 떠오르지 않았고 왼쪽으로 이동, 오른쪽으로 이동을 비교했었다.
- 특정 테스트 케이스에서 오류 발생…
구글링을 했고, 대부분의 풀이에서 cur + len - nxt + min(cur, len - nxt)를 사용하고 있었다.
- 그러나 왜 저렇게 되는지에 대한 언급이 없어 내가 직접 증명을 하게 되었다.
나에게는 간단한 로직이 누군가에게는 쉽게 이해하지 못하는 로직일 수 있다는 생각이 들었다.
- 포스팅 할 때 좀 더 신경써야 겠다고 느꼈다.

Programmers. 조이스틱

1. 문제설명

2. 입/출력

3. 문제 분류

4. 알고리즘 설계

5. 전체 코드

6. 소감