[프로그래머스]조이스틱 C++ 문제풀이, 그리디 알고리즘(Greedy)

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

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

이 문제에서 제일 어려웠던 부분은 문제를 이해하는 것이었다.

 

처음에는 전부 'A' 로 세팅되어있는 문자열을 가지고 있다.

 

그리고 이 문자열을 인자로 들어오는 문자열로 바꿔야하는데 그 최소 횟수를 구하는 것.

 

a -> b -> c -> d .... z  반대로 a -> z  -> y -> x  이런식으로도 갈 수 있다.

 

그리고 문자는 대문자만 사용한다는 조건이 있으니 대놓고 아스키 코드를 이용하라는 문제이다.

 

아스키 코드 범위는 65~90  ,

 

문자 변환 횟수가 ( 90 - 65 ) / 2   보다 값이 높다면 반대로 가는게 더 횟수가 적다는 뜻이다. 

 

마찬가지로 커서위치도  <- , -> 움직일 수 있다.

 

이렇게 조건이 있고 이 조건들을 가지고 가장 최소 횟수를 계산하면 되는데, 말 그대로 그리디하게 접근하면 풀리는 문제이다.

 

1. 커서 기준에서 바꿔야하는 가장 가까운 문자 위치로 이동 

2. 바꿔야할 알파벳으로 바꾸는 최소 횟수 찾기 

3. 커서 위치 갱신 

반복 

 

int solution(string name)
{
    int answer = 0;
    
    char*str = new char[name.length()+1];
    memset(str, 'A', sizeof(char)*name.length());
    str[name.length()] = '\0';
    int cur=0;
    int idx=0;
    
    while(strcmp(str, name.c_str())!= 0)
    {
        int minDis = 20; // name의 최대 길이가 20으로 제한
        for(int i=0; i<name.length(); i++)
        {
            if(name[i]==str[i])
                continue;
            
            int dis = min(abs(cur - i), abs(((int)(name.length()-1)- i+ cur + 1)));
            if(dis < minDis)
            {
                idx=i;
                minDis = dis;
            }
        }
        cur=idx;
        answer += minDis;

        int targetCode = name[cur];
        int curCode = str[cur];
       
        int minCnt = min(abs(targetCode-curCode), abs(90-targetCode+1));
        
        answer += minCnt;
        str[cur]=name[cur];
   
    }
    
    delete [] str;
    return answer;
}

 

 

문자열을 전부 순회해서 바꿔야할 문자열을 찾고 그 문자열 중에 → 방향 ← 방향을 계산해서 가장 짧은 이동 횟수를 가진 문자열 위치로 이동한다

int dis = min(abs(cur - i), abs(((int)(name.length()-1)- i+ cur + 1)));

문자열의 아스키 값을 비교한다 아스키 범위는 65~90 , 거꾸로도 조이스틱을 움직일 수 있으니 마찬가지로 반대 방향으로도 계산해준다.

int minCnt = min(abs(targetCode-curCode), abs(90-targetCode+1));