[C++ 알고리즘] 프로그래머스 : 조이 스틱

 


Greedy

조이 스틱

풀이과정

알파벳 위 아래로 조작하는 건 알겠고, 단순히 오른쪽으로 쭉 이동하거나 왼쪽에서 쭉 이동하는 것만 비교해서 제출했더니 11번 테케에서 오류나서 구글링의 힘을 빌렸다..

간단한 건데도 이해하기 힘들어서 직접 써서 증명하면서 풀었다 ㅠㅠ 그리디 넘 어려웡


  1. name[i]에서 가장 가까운 A가 아닌 문자 name[ind] 찾기
  2. 여기서 조이스틱을 움직이는 최단 경로는
    (1) 원점 –> i –> 원점 –> ind
    (2) 원점 –> ind –> 원점 –> i
    이렇게 두 가지이다.
  3. 따라서 (i : 0~name.length)에 대해 조이스틱을 움직이는 최소값을 구한다.


반례인 “ABABAAAAABA”에 대해 위 풀이를 수식으로 설명해보면 다음과같다.


코드

#include <algorithm>
#include <string>

using namespace std;

int solution(string name) {
    int answer = 0;
    int n = name.length();
    int turn = n - 1; //조이스틱을 한 방향으로 쭉 움직였을 때
    for (int i = 0; i < n; i++) {
        if (name[i] - 'A' < 14) answer += name[i] - 'A';
        else answer += 'Z' - name[i] + 1;

        int ind = i + 1;
        while (ind < n && name[ind] == 'A') ind++;

        turn = min(turn, i + n - ind + min(i, n - ind));
    }

    answer += turn;
    return answer;
}


:bookmark: REFERENCE
[프로그래머스] 조이스틱