(프로그래머스 c++)조이스틱

탐욕법을 이용하여 문제를 풀어야 한다..!

 

우선 변수를 여러 개 선언하였다.

string s 는 while문을 탈출하기 위한 조건으로, name을 모두 'A'로 바꿨을 때 탈출하도록 하였다.

그래서 s에는 name 길이만큼 'A'를 넣어주었다.

 

int형 변수로는 name의 길이를 나타내는 size,

현재 인덱스의 위치를 나타내는 current,

오른쪽으로 움직이는 횟수를 나타내는 right,

오른쪽으로 움직였을 때 바꿔야 하는 인덱스를 나타내는 go,

왼쪽으로 움직이는 횟수를 나타내는 left,

왼쪽으로 움직였을 때 바꿔야 하는 인덱스를 나타내는 back

이다.

 

while문으로 name이 모두 'A'로 바꿔질 때까지 반복하도록 한다.

그리고 크게 if문을 잡았는데 현재 name[current]가 'A'인지 아닌지를 판별한다.

만약 name[current] == 'A'이면 오른쪽, 왼쪽으로 갔을 때 최소 거리를 구하여 움직이도록 해야 하고,

'A'가 아니라면 현재 위치에 있는 알파벳의 최소 조작 횟수를 answer에 더하고 'A'로 바꿔준다.

 

핵심적인 부분은 name[current]가 'A'가 아닐 때이다.

탐욕법은 현재 위치에서 최선의 방법을 생각해야 하기 때문이다.

go와 back을 이용하여 현재 위치에서 움직여야 하는 최소 거리를 구하였다.

(20, 22번째 줄 참조)

그리고 go가 current보다 작은 경우

(위의 사진에서 go는 8, current는 9이다.)

이 때는 go + size - current를 하여 오른쪽으로 움직였을 때의 거리를 구하였다.

go가 큰 경우는 go - current를 하여 거리를 구하면 된다.

back도 go와 같은 원리로 생각하여 거리를 구하면 된다.

 

그리고 right와 left를 비교하여 최소 거리를 구한 후 answer에 right or left를 더하고,

현재 위치인 current를 go or back으로 바꿔주면 된다..!

 

2단계 치고는 상당히 까다로운 문제인 것 같다..!

#include <string>
#include <vector>
#include <iostream>

using namespace std;

int solution(string name) {
    int answer = 0;
    string s = "";
    int size = name.size(), current = 0, right = 0, left = 0;
    int go = 0, back = size - 1;
    
    for(int i = 0; i < size; i++)
        s += 'A';
    
    while(s != name)
    {
        if(name[current] == 'A')
        {
            while(name[go] == 'A')
                go++;
            while(name[back] == 'A')
                back--;
            
            if(go < current)
                right = go + size - current;
            else
                right = go - current;
            
            if(back < current)
                left = current - back;
            else
                left = size - back + current;
            
            if(right <= left)
            {
                answer += right;
                current = go;
            }
            else
            {
                answer += left;
                current = back;
            }
        }
        else
        {
            answer += name[current] - 'A' < 'Z' - name[current] + 1 ? name[current] - 'A' : 'Z' - name[current] + 1;
            name[current] = 'A';
        }
    }
    return answer;
}