Programmers > 코딩테스트 연습 > 탐욕법 > 조이스틱

문제링크 : https://programmers.co.kr/learn/courses/30/lessons/42860

풀이

이 문제를 복잡하지 않게 풀기 위해서는 조이스틱으로 이름을 만드는 경우의 수가 2가지라는 

것을 먼저 파악하는 것이 중요하다.

이 2가지 경우의 수에는 맨 처음 문자를 수정한 뒤 맨 끝으로가서 이름을 만들기 시작하는 경우와

맨처음부터 그냥 순서대로 끝까지 이름을 만드는 경우가있다.

난 이 2가지를 모두 구현하고 두 방법중 조이스틱을 움직인 횟수가 적은걸 return하도록 하였다.

유의할 점으로는 예를들어 'ABCAA'라는 문자를 처음부터 순서대로 만든다고 했을 때 

'C'를 만든뒤 뒤에 있는 문자들은 모두 'A'이기 때문에 이대로 더이상 조이스틱을 움직이지 않아도 

된다는 것을 반영해야 한다는 점이다.

아래는 위에서 설명한 것을 통해 구현한 코드이다.

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

using namespace std;

int solution(string name) {
    int answer1 = 0; //처음부터 커서를 오른쪽으로 이동시켜가며 조작할 횟수
    int answer2; //처음부터 커서를 왼쪽으로 이동시켜가며 조작할 횟수

    answer1 += min(name[0]-'A','Z'-name[0]+1); //두 번째 혹은 마지막으로 이동
    answer2 = answer1;

    for(int i=1; i<name.size(); i++)
    {
        bool b = true;
        for(int j=i; j<name.size(); j++){
            if(name[j] != 'A'){
                b = false; break;
            }
        }
        if(b) break;
        answer1++;
        answer1 += min(name[i]-'A','Z'-name[i]+1);
    }
    for(int i=name.size()-1; i>=1; i--)
    {
        bool b = true;
        for(int j=i; j>=1; j--){
            if(name[j] != 'A'){
                b = false; break;
            }
        }
        if(b) break;
        answer2++;
        answer2 += min(name[i]-'A','Z'-name[i]+1);
    }
    return min(answer1,answer2);
}