[알고리즘문제] 프로그래머스 - 조이스틱

문제를 보니깐 JAVA로 예전에 푼 흔적이 있었다. 정답을 맞춘 흔적이 없는 걸 봐선 그떄 못 푼 문제 같았다. 

 

문제해결방법은 먼저 그리디하기 생각했다. 내 알파벳을 바꾸고 현재 나의 위치에서 가장 가까운 놈을 먼저 찾아가는 것이다.

 

#include <string>
#include <vector>
#include <iostream>
#include <stdlib.h>

using namespace std;

int getMinLength(int start,string name){
    
    int left = name.at(start);
    int right = name.at(start);
    int depth = 0;
    
    while(true){
        if(left == 65 || right == 65){
            break;
        }
        depth++;
        right++;
        left--;
        
        if(right > 90){
            right = 65;
        }
    }
    
    return depth;
}

int solution(string name) {
    
    int answer = 0;
    
    string str="";
    
    int max = name.size()-1;
    int min = 0;
    
    for(int i=0;i<name.size();i++){
        str+="A";
    }
    
    int start = 0;
    int left,right;
    
    while(true){
        
        left = start;
        right = start;
        
        if(name.at(start) != 'A'){ 
            answer += getMinLength(start,name); // 위 / 아래로 움직임
            name.replace(start,1,"A");
        }
        
        if(str == name){
            break;
        }
        
        int mov = 0;
        while(true){ // 좌 / 우로 움직임
            
            left--;
            right++;
            mov++;
            
            if(left < min){
                left = max;
            }
            
            if(right > max){
                right = min;
            }
            
            if(name.at(right) != 'A'){
                answer += mov;
                start = right;
                break;
            }
            
            if(name.at(left) != 'A'){
                answer += mov;
                start = left;
                break;
            }
        }
    }
    
    return answer;
}

 

 

전체 코드는 while문 하나에서 동작하고 name의 모든 알파벳이 "A"가 되면 while문을 종료한다.

 

먼저, 조이스틱을 위 / 아래로 움직이는 경우를 먼저 계산하였다. 계산을 마치면 현재의 알파벳을 "A"로 바꾼다.

여기서 처음에는 그냥 answer += abs(number.at(start) - 'A')를 했는데, 이러니깐 답이 안나왔다. 다시 생각해보니, 이렇게 코드를 짜면 'Z'를 'A'로 바꿀 때 1번 이면 되는데 15번의 결과가 나오게 된다. Z,Y,X...이런식으로 A를 찾아가는...

그래서 getMinLength()라는 함수를 만들어서 왼쪽 / 오른쪽으로 움직이면서 'A'를 찾아가는 방법을 사용했다.

 

조이스틱을 좌 / 우로 움직이는 경우도 마찬가지로 현재 위이(start)에서 왼쪽 / 오른쪽으로 움직이면서 'A'가 아닌 곳을 검사하는 방법을 사용했다. 먼저 왼쪽을 검사하고 오른쪽을 검사하는 방법을 사용하니깐 마지막 테스트케이스가 실패로 나왔다. 오른쪽을 먼저 검사하니깐 문제가 해결되었다.