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

https://programmers.co.kr/learn/courses/30/lessons/42860

코딩테스트 연습 - 조이스틱

level2

알파벳으로 구성된 문자열이 주어지고, A로만 이루어진 동일한 길이의 문자열을 주어진 문자열과 동일하도록 바꾸려면

알파벳을 바꾸는 조이스틱 방향과, 커서를 이동하는 조이스틱 방향을 몇번 조작해야하는지

그 최솟값을 구하는 문제

 

어려웠다 ^_^

 

접근방법

알파벳 변경을 위한 조이스틱 조작 횟수는 A부터 Z방향으로 이동하는 경우와, A에서Z로 이동한 다음 Z->A방향으로 이동하는 경우만 비교하면 된다. (X-A, Z-X+1)을 비교하면 됨

 

문제는 커서 이동 조작 횟수였다.

예를 들어 만들어야 하는 문자열에 A가 연속적으로 포함되어 있을 경우 순방향, 역방향, 왔다가 되돌아가는 경우를 모두 비교해야 한다.

혼자 고민한 후에 테스트케이스 몇개가 통과가 안돼서 구글링 해봤는데, 테스트케이스가 바뀐지 얼마되지 않아서 통과되지 않는 레퍼런스가 많았다.

 

키 아이디어는 이 문제가 그리디 문제라는 점..

풀이한 방법은

0. 커서 이동 조작 횟수를 count라고 하겠다. count는 최악의 경우 문자열의 모든 문자를 방문하는 것이므로 이 경우 조이스틱을 n-1번 조작하게 된다. 따라서 count의 초기값은 n-1이다. (n은 문자열의 길이) 지금부터 이 값 보다 적은 값이 나오면 갱신한다.

1. 문자열의 문자들을 처음부터 하나씩 방문한다.

2. 현재 위치(i)에서 다음 문자부터 A가 얼만큼 연속된지 카운팅한다.

3. 더이상 A가 아닌 위치를 ii 인덱스 위치에 저장한다. 

4. 0~i 까지를 길이 a(= i)라고 하고, ii~n까지의 길이를 b(=n-ii = (n-1)-ii+1, 이때 +1은 0번에서 마지막 위치로 이동하는 횟수)라고 한다.

5. 이제 2a+b (순방향으로 갔다가 돌아와서 역방향으로 ii까지 가는 경우), a+2b (처음부터 역방향으로 갔다가 0번째로 돌아와서 다시 순방향으로 i까지 가는 경우) 를 비교하여 count 값보다 작으면 count값을 갱신한다.

6. 문자열의 모든 문자에 대해 이 동작을 반복한다.

7. 반복문을 마치면 count에는 커서위치 변경을 위한 최소 조작횟수가 담겨있다.

 

+ 알파벳 변경 조작 횟수를 더해서 리턴

 

소스코드

#include <algorithm>
#include <string>

using namespace std;

int solution(string name) {
    int n = name.size();
    int upDown = 0;
    int leftRight = n-1;
    
    for(int i = 0 ; i < n ; i++){
        upDown += min(name[i]-'A', 'Z'-name[i]+1);
        
        int ii = i+1;
        while(ii < n && name[ii] == 'A')
            ii++;
        
        int newLeftRight = i + n-ii + min(n-ii, i);

        leftRight = min(leftRight, newLeftRight);
    }
    
    return upDown + leftRight;
}