[그리디, 난이도 중] 프로그래머즈, 조이스틱

해결 방법

먼저 조이스틱의 상하 이동 횟수들을 모두 합산해놓고 좌우 이동 횟수만 추가로 더하는 방식이 간편하다.

알파벳의 개수가 총 26개라는 점을 잘 이용하면 상하 이동 횟수를 구하는 것은 간단하지만, 조이스틱의 좌우 이동 횟수를 구하는 것은 쉽지 않을 수 있다.

 

조이스틱의 최소 좌우 이동 횟수는 다음과 같이 2가지 경우로 나누어야 한다.

• 한쪽으로만 이동하는 경우(오른쪽, 왼쪽)
• 중간에 한 번 꺾는 경우(오른쪽->왼쪽, 왼쪽->오른쪽)

즉, 한 방향으로만 커서를 이동하는 경우 외에도 중간에 한 번 꺾어야 하는 경우도 고려해야 한다. 물론, 두 번 이상 꺾는 경우는 최소 좌우 이동 수가 될 수 없다.

예를 들어, "BABAAAAAAAAAABAB" 의 경우를 살펴보자.

오른쪽으로만 이동하는 경우에는 4번째 'B'까지 15번을 이동해야 하고, 왼쪽으로만 이동하는 경우에는 2번째 'B'까지 14번을 이동해야 한다.

그러나 2번째 'B'까지는 오른쪽으로 이동했다가 3번째 'B'까지 왼쪽으로 이동하는 경우에는 7(2+2+3)번만 이동하면 되고, 3번째 'B'까지는 왼쪽으로 이동했다가 2번째 'B"까지 오른쪽으로 이동하는 경우에는 8(3+3+2)번만 이동하면 된다.

이 중 최소 좌우 이동 횟수는 7이다.

 

 

소스코드

#include <string>
#include <vector>
using namespace std;

vector<int> correct; // 수정을 위해 방문할 자리의 인덱스들을 모은 벡터

int solution(string name) {
    int answer = 0;
    int convert; //문자->정수 변환
    for(int i=0;i<name.length();i++){
        convert = (int)name[i]-65; //A=0~Z=25로 계산
        if(convert!=0&&i!=0) correct.push_back(i);
        answer+=min(convert,26-convert); //조이스틱의 상하 이동 횟수 합산
    }
    if(correct.size()==0) return 0;
    
    int min_moves=21;
    // 한쪽으로만 이동하는 경우(오른쪽, 왼쪽)
    min_moves=min(min(min_moves, correct[correct.size()-1]), (int)name.length()-correct[0]);
    // 오른쪽으로 이동했다가 왼쪽으로 이동하는 경우
    for(int i=1;i<correct.size();i++) min_moves=min(min_moves, 2*correct[i-1]+(int)name.length()-correct[i]);
    // 왼쪽으로 이동했다가 오른쪽으로 이동하는 경우
    for(int i=1;i<correct.size();i++) min_moves=min(min_moves, 2*((int)name.length()-correct[i])+correct[i-1]);
    return answer+min_moves;
}

 

테스트케이스 27개 모두 통과