프로그래머스 - C++ 조이스틱

Greedy를 이용하여 해결하는 문제이다. 조이스틱의 위/아래 방향 이동은 간단하게 해결하였지만, 오른쪽/왼쪽 방향 이동이 이 문제의 핵심이다. 다음은 조이스틱을 오른쪽/왼쪽으로 이동할 지 결정하는 방법이다.

 

오른쪽/왼쪽 이동횟수가 최소가 되는 상황은 아래의 3가지 이다.

1. 한쪽 방향으로만 이동할 때가 최소 ex)JEROEN

2. 'A' 로만 이루어진 문자열의 왼쪽을 먼저 탐색한 뒤 되돌아가 오른쪽을 탐색할 때가 최소 ex) BBAAAAAAABBBB

3. 'A' 로만 이루어진 문자열의 오른쪽을 먼저 탐색한 뒤 되돌아가 왼쪽을 탐색할 때가 최소 ex) BBBBAAAAAAABB

 

1번의 경우, 이동횟수는 name.length() - 1 이 될 것이며,

2번의 경우, 왼쪽탐색 + 왼쪽탐색 + 오른쪽탐색

3번의 경우, 오른쪽탐색 + 오른쪽탐색 + 왼쪽탐색이 된다.

따라서 1, 2, 3번 값 중 가장 작은 값이 답이 된다.

 

---

1. Solution 코드

#include <string>
#include <vector>

using namespace std;

int solution(string name) {
    int answer = 0;
    int shift = name.length() - 1; //오른쪽 방향으로만 이동했을 경우, 오른쪽 조이스틱 이동 횟수
    
    for(int i = 0; i < name.length(); i++){
        if(name[i] - 'A' < 14)
            answer += name[i] - 'A';
        else
            answer += 'Z' - name[i] + 1;
        
        if(name[i] == 'A'){
            int target = i;
            
            while(target < name.length() && name[target] == 'A')
                target += 1;    //A로만 이루어진 문자열 찾기
            int left = i == 0?0:i-1;    //찾은 문자열 왼쪽에서의 이동횟수
            int right = name.length() - target;   //찾은 문자열 오른쪽에서의 이동횟수
            shift = min(shift, left + right + min(left, right));
        }
        
    }
    answer += shift;
    return answer;
}

 

2. 알아야 할 개념

Greedy 문제를 구별하는 방법은, 선택의 순간에 하나의 노드로 이동하여도 해답을 도출할 수 있을 경우 Greedy를 이용한다. Greedy 문제는 코딩테스트 난이도 중 높은 난이도에 속하고, 많은 연습을 요구한다.