[프로그래머스] 조이스틱 - 그리디 (탐욕법) / C++

✅ 프로그래머스 조이스틱
https://programmers.co.kr/learn/courses/30/lessons/42860

문제 설명 및 제한 사항

프로그래머스에서 탐욕법 으로 분류되어있는 문제이다.

이 문제가 그리디인 이유는,

(1) A에서 바꿀 알파벳 문자까지 가는상황에서 Z에서부터 거꾸로 갈 수도 있고, A부터 순서대로 갈 수 있으므로 그 중 그때그때 최소 횟수가 될 수 있는값을 선택하며 진행하기 때문

(2) 또한 한문자를 바꾸고 난 후에, 커서를 이동하는 상황에서 왼쪽으로 커서를 이동할지, 오른쪽으로 커서를 이동할지 선택할 수 있으므로 그때그때 또 최소 횟수가 될 수 있는 값을 선택하며 진행해 나가게 된다.

그리디 알고리즘은, 매 선택에서 지금 이 순간 당장 최적인 답을 선택하여 적합한 결과를 도출해나려는 의도를 가지고 있다.
하지만 위의 그림처럼 그리디 알고리즘을 사용하면 매 선택이 그 순간에 대해서는 최적이지만 종합적으로 봤을 땐 최적해를 보장해 주지는 않는다!

문제 풀이 과정

1. 주어진 name의 길이만큼을 A를 이어붙여 초기세팅을 해준 initial_name을 만든다.

2. 인덱스를 0번부터 잡아서, 조이스틱 조작을 시작한다

3. AAA (initial_name) 와 JAZ (name:우리가 만들어야할 값) 에서 인덱스 0부터 비교해나가면서, A->J로 조작하는것이 빠를지(조이스틱 윗방향) Z->J로 조작하는것이 빠를지(조이스틱 아랫방향) 최소값을 구해서 이동횟수를 return할 answer변수에 더해준다.

 answer += min(name[current_index] - 'A', 'Z' - name[current_index] + 1);

4. 다 바꾼후에는 initial_name에 완료했다는 표시를 남기기위해 initial_name을 name에 해당하는 알파벳으로 바꿔준다.

initial_name[current_index] = name[current_index];

5. 다음바꿀 문자로 이동하기 위해 커서를 이동한다.

   이때 문자가 같을 경우에는, 알파벳을 바꿀 필요가없으므로 커서를 계속 이동시킨다.

   커서를 왼쪽 또는 오른쪽으로 움직일 수 있기때문에,
   왼쪽으로 움직이는 경우와 오른쪽으로 움직이는 경우 중 더 적게 움직이는 방향을 최종적으로 택한다.

	ex) 왼쪽으로 이동하는 경우, (오른쪽도 방식 동일)

	int left_index = current_index;
        int left_cnt = 0; //왼쪽이동횟수
        
        while(initial_name[left_index] == name[left_index])
        {//문자가 같을 경우에는, 알파벳을 바꿀 필요가없으므로 커서를 계속 이동시킨다.
            left_index--;
            left_cnt++;
            
            // 왼쪽으로 이동시에 범위를 벗어나는 경우
            if(left_index == -1)
            {
                //첫번째 문자의 커서위치에서 왼쪽으로 이동하는경우, 마지막 문자위치로 커서를 옮겨줘야함.
                left_index = name.size()-1;
            }
        }

initial_name이 name이 될 때 까지, 3~5번 과정을 반복한다.

---

최종 코드

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

#include <string>
#include <vector>
#include <algorithm>
using namespace std;
 
int solution(string name) 
{
    int answer = 0;//이동 횟수
    string initial_name;
    
    for(int i = 0; i < name.size(); i++)
    {
        //주어진 이름의 길이만큼 A를 이어붙여서 초기세팅을 해줌
        initial_name += "A";
    }
    
    int current_index = 0;
    while(true)
    {   
        answer += min(name[current_index] - 'A', 'Z' - name[current_index] + 1);
        //조이스틱을 윗방향 또는 아랫방향으로 움직였을때의 최소값을 answer에 더해나감
        // 아래방향으로 움직여야될때는 한번을 더 더해줌 (왜냐면, z에서 바로가는게 아니라 a에서 z로 가는것도 한번 더 더해줘야되므로)
        initial_name[current_index] = name[current_index];
        //nowIdx에 해당하는 알파벳문자는 조이스틱으로 바꿔놓기 완료!

        if(initial_name == name)
        {
            return answer;
        }
        
        // 1. 왼쪽 이동 횟수 구하기
        int left_index = current_index;
        int left_cnt = 0; //왼쪽이동횟수
        
        while(initial_name[left_index] == name[left_index])
        {//문자가 같을 경우에는, 알파벳을 바꿀 필요가없으므로 커서를 계속 이동시킨다.
            left_index--;
            left_cnt++;
            
            // 왼쪽으로 이동시에 범위를 벗어나는 경우
            if(left_index == -1)
            {
                //첫번째 문자의 커서위치에서 왼쪽으로 이동하는경우, 마지막 문자위치로 커서를 옮겨줘야함.
                left_index = name.size()-1;
            }
        }
        
        // 2. 오른쪽 이동 횟수 구하기
        int right_index = current_index;
        int right_cnt = 0; //오른쪽이동횟수
        
        while(initial_name[right_index] == name[right_index])
        {//문자가 같을 경우에는, 알파벳을 바꿀 필요가없으므로 커서를 계속 이동시킨다.
            right_index++;
            right_cnt++;
            
            // 오른쪽으로 이동시에 범위를 벗어나는 경우
            if(right_index == name.size())
            {
                //마지막 문자의 커서위치에서 오른쪽으로 이동하는경우, 첫번째 문자위치로 커서를 옮겨줘야함
                right_index = 0;
            }      
        }
    
        // 3. 왼쪽, 오른쪽 중 횟수가 최소인 방향을 선택
        if(left_cnt < right_cnt)
        {// 왼쪽이 최소일경우
            answer += left_cnt;
            current_index = left_index;
        }
        else
        {// 오른쪽이 최소일경우
            answer += right_cnt;
            current_index = right_index;
        }
    }
}

왼쪽, 오른쪽 커서를 움직이는 상황중 어느것이 최소인지 계산할때
min을 이용하면 시간초과가 난다.
이건 왜 그런지 모르겠다 😭

끝 ✨