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

< 해설 >

보통 질문하기에 질문이 50~60 개가 넘어가는 순간 문제에서 설명이 충분하지 않구나를 느끼게 된다.

문제 해결에 어려움을 느끼면 (보통 이해가 안되면) 질문하기에 들어가서 사람들이 적어놓은 반례나 예상 테스트 케이스, 예외에 대해서 쭉 살펴보고 코드를 다시 짜는데 이 문제는 이게 왜 그리디냐고 묻는 사람도 있고 재귀로 구현한 사람도 있고 난리다. ㅋㅋ

 

문제를 1시간정도 풀다가 다른 사람의 풀이가 너무너무너무 궁금해서 여러 블로그도 찾아봤는데 테스트 케이스 수정이 들어가기 전 코드들은 실패로 뜨는것들도 많다. 

내가 찾은 블로그의 글은 알파벳 맞추기 / 순서 이동 을 따로 계산하셨다.

알파벳 맞추는 부분은 모두가 똑같이 구현했으리라 생각한다. 그래서 이 부분은 생략..

 

역순으로 가지 않고 순차적으로 문자 정렬이 일어나면 조이스틱은 왼쪽으로 name.size()-1 만큼 이동한다. 이 이동횟수를 기준으로 두고, 좌우 이동을 판별하는 것!

 

AABAAAAAAAAB 같이 갔다가 돌아와야하는 케이스에 대한 체크가 무조건 필요한 문제이다.

참고한 블로그의 글을 보면 수학 수식으로 푸셨는데 (ㄷㄷ;;) i->ind 로 무조건 간다고 하면 두개의 케이스로 나뉘게 된다.

무조건 원점에서 시작하고 (동일하게 체크하기 위해) 시작부터 첫번째 b까지가 X, 끝부터 마지가 B 까지가 Y 라고 하면 

첫번째 그림의 수식은 X + X + Y 이고

두 번쨰 그림의 수식은 Y + Y + X 가 된다. 

 

두개의 수식에서 더 작은 것을 찾으면 된다! 그리디 이므로 name.size()-1 한 것보다 현재 탐색이 작다면 그것을 선택한다.

이런식으로 풀이하면 그리디를 만족하는 조이스틱의 최소 움직임을 알 수 있다.

(혹시 그러면 정상 순열으로 이동하는게 만족하지 않나요 라는 궁금증이 생길수도 있는데 정상순열일때는 X+Y가 name.size()가 되어 버리므로 기존의 name.size()-1 을 해치지 않는다.)

 

 

< 문제 >

 

< 풀이 >

#include <string>
#include <vector>

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 idx = i + 1;

        while (idx < n && name[idx] == 'A')
            idx++;

        int minCheck = i + n - idx + min(i, n - idx);

        turn = min(turn, minCheck);
    }

    answer += turn;
    return answer;
}