Programers : 조이스틱 (greedy)

조이스틱

코드

#include <string>
#include <vector>

using namespace std;

int solution(string name) {
    int answer = 0,i=0;
    string str ="";
    /* str 초기화 */
    for(int i=0;i<name.length();i++) str+="A";
    while(name != str)
    {
        char ch = name[i];
        /* 조이스틱을 올릴지, 내릴지에 대해 최소값으로 빼기! */
        int dif = min(ch-'A', 'Z'-ch+1);
        answer += dif;
        /* 바꾸어야 할 값을 A로 치환 --> 밑에서 A가 아닌 요소로 값을 찾기 때문! */
        name[i] = 'A';
        if(name == str) break;
        /* 앞으로 갈지, 뒤로 갈지 정함! --> A가 아닌 요소가 먼저 나오면 break! */
        for(int k=1;k<=name.length()/2;k++){
            int prev_idx = i-k < 0 ? i-k+name.length() : i-k;
            int next_idx = i+k > name.length()-1 ? i=i+k-name.length() : i+k;
            if(name[next_idx] != 'A') {
                i = next_idx;
                answer += k;
                break;
            }
            else if(name[prev_idx] != 'A'){
                i = prev_idx;
                answer += k;
                break;
            }
        }
    }
    return answer;
}
  • key point!
    1) 조이스틱을 위/아래로 움직이는 것의 선택은 min을 이용해 해결
    2) 조이스틱을 왼쪽/오른쪽 으로 움직이는 것의 선택은 먼저 'A'가 아닌 요소가 발견할 때 까지 찾기
    --> 바꾼 name의 값을 'A'로 치환해주는 작업이 필요!

좋은 웹페이지 즐겨찾기