프로그래머스 조이스틱 [Lv. 2] (C++)

프로그래머스

다음 알파벳, 이전 알파벳, 커서 이동 기능이 있고, string으로 이름을 입력 받을 때, 이름을 입력하기 위한 최소 기능 사용횟수를 찾아주세요 (최초 알파벳은 A로만 이루어져 있습니다.)

 

풀이방법

A에서 특정 문자로 넘어가기 위한 최소 비용은 양쪽 방향중 더 가까운 쪽을 선택하면 됩니다. 코드로 표현하면 아래와 같습니다.

vector<int> costs('Z'-'A'+1);
for (int i = 0; i < costs.size(); i++)
    costs[i] = min(i, 26 - i);

 

 

이 문제의 핵심은 커서의 최소 이동 횟수에 있습니다.

 'K K A A A A K K" 를 입력 받을 때 커서를 오른쪽으로만 이동하면 7회가 나오지만

1번 문자까지 이동 후 왼쪽으로 이동하여 7번 문자로 이동한다면 이동 홧수 4회로 최소 비용을 구할 수 있습니다.

 

정리해보겠습니다.

1. A를 사이에 두고 있는 문자의 위치를 찾습니다. 위 문자열에서는 2번과 7번 문자입니다.

2. 두 문자 사이의 A를 제외하고 탐색하는 경우의 수를 생각해봅니다.

3. 위 문자열을 예시로 2번 먼저 탐색 후, 왼쪽으로 이동하여 7번을 탐색하는 경우가 있고, 원점에서 시작하여 7번을 먼저 탐색 후 오른쪽으로 이동하여 2번을 탐색하는 두개의 경우가 있겠습니다.

 

코드로 표현하면 아래와 같습니다.

int case1 = left*2 + (size - right);
int case2 = left + (size - right)*2;
minMove = min(minMove, min(case1, case2));

 

 

정답 코드

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

int solution(string name){
    vector<int> costs('Z'-'A'+1);
    for (int i = 0; i < costs.size(); i++)
        costs[i] = min(i, 26 - i);
    
    int ans = 0;
    int size = name.size();
    
    int minMove = size-1;
    for(int left = 0; left < size; left++)
    {
        ans += costs[name[left]-'A'];
        int right = left + 1;
        
        while(right < size && name[right] == 'A') 
            right++;
        
        int case1 = left*2 + (size - right);
        int case2 = left + (size - right)*2;
        minMove = min(minMove, min(case1, case2));
    }
    ans += minMove;
    return ans;
}