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

1. 문제

 

조이스틱을 다음과 같이 조작하여 AA...A 에서 이름을 기록하는 최소의 조작 수를 구하여라

 

위 = 알파벳 다음글자       (Z->A)

아래 = 알파벳 이전 글자   (A->Z)

왼쪽 = 커서 왼쪽으로       (맨 왼쪽 => 맨 오른쪽)

오른쪽 = 커서 오른쪽으로 (맨 오른쪽 => 맨 왼쪽)

 

2. greedy

이문제는 그리디로 푸는 문제가 아닌것같지만 그리디 항목에 있어서 그리디로 풀었다.

 

그리디는 최소임을 보장하지 않는다.

 

"CANAAAAANAN" 의 경우 최소는 48이지만

 

그리디한 방법 현재상태에서 최선을 선택하면 49가 나온다고한다

 

 

#include <string>
#include <vector>
 
using namespace std;
 
int alphabetMove[26];
 
void calcAlphabetMove()
{
    int move = 0;
    alphabetMove[0] = 0;
    while(++move <= 13)
        alphabetMove[move] = alphabetMove[26 - move] = move;
}
 
void initialize(string& name, vector<bool>& visited, int &n)
{
    for(int i = 0; i < name.size(); i++)
        if(name[i] == 'A')
        {
            visited[i] = true;
            n++;
        }
}
 
int findNext(string& str, int cursor, vector<bool>& visited, int& answer)
{
    string tmp = str + str + str;
    int current = cursor + str.size();
    int left, right;
    for(int i = current + 1; i < tmp.size(); i++)
        if(tmp[i] != 'A' && !visited[i%str.size()])
        {
            right = i;
            break;
        }
        
    for(int j = current - 1; 0 <= j; j--)
        if(tmp[j] != 'A' && !visited[j%str.size()])
        {
            left = j;
            break;
        }
    
    answer += min(right - current, current - left);
    
    return ((right - current > current - left) ? left: right)%str.size();
}
 
 
int solution(string name) {
    int answer = 0, n = 0, cursor = 0;
    vector<bool> visited(name.size(), false);
    
    calcAlphabetMove();
    initialize(name, visited, n);
    
    while(n < name.size())
    {
        if(visited[cursor])
        {
            cursor = findNext(name, cursor, visited, answer);
            continue;
        }
        answer += alphabetMove[name[cursor] - 'A'];
          visited[cursor] = true;
        n++;
    }
    
    return answer;
}

 

3. 더 나은 코드

   int left_right = len - 1;
    for (int i = 0; i < len; ++i) {
        int next_i = i + 1;
        while (next_i < len && name[next_i] == 'A')
            next_i++;
        left_right = min(left_right, i + len - next_i + min(i, len - next_i));
    }

이 코드는 다른사람 풀이 첫번째로 나오는 코드이다.

먼저 알파벳에서 조작하는 횟수를 전부 더하고 왼쪽 오른쪽 횟수를 더하여 답을 구하는 방법이다.

 

왼쪽 오른쪽 이동횟수의 최대는 그냥 왼쪽이나 오른쪽으로 쭉 가는것 즉 len - 1이다.  

 

for문의 요소들은 다음과 같다.

 

i = 커서를 왼쪽에서 i까지 이동한 거리

    (맨왼쪽 에서 오른쪽으로 이동한 횟수)

next_i = i 다음 위치(A가 아닌)

 

즉 i ~ next_i 의 사이는 커서가 지나가지 않는 구역이다.

중간에있는 A는 스킵하는 구간이 넓어야 최소가 된다는 것이다.

 

len - next_i = 왼쪽으로 이동한 횟수 

i = 오른쪽으로 이동한 횟수

min(i, len - next_i) = 작은쪽을 먼저 이동해야 최소가 된다.

                           (작은쪽 방향으로 이동한후 원점으로 간뒤 다시 다른방향으로 ) 

 

이를 모든 i에 대해 값을 최소로 업데이트 시키면 답을 얻을 수 있다. 

 

이 문제에서 그리디로 이동하는것은 한번의 방향 전환만 있음을 의미한다.

그렇지 않으면 중복된 부분을 많이 지나게 되기 때문이다.

 

 

 

 

 

 

코딩테스트 연습 - 조이스틱 | 프로그래머스 (programmers.co.kr)