[프로그래머스, C++] 조이스틱

문제 링크

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

 

 

 

풀이

두 가지의 부분해가 존재한다.

1. 상, 하 커서를, 바뀔 알파벳이 디폴트 'A'에서 최소로 조작한다.

2. 좌, 우 커서를, 디폴트 'A'가 아닌 곳과의 거리가 최소로 조작한다.

 

deque을 사용하여 pop_front()와 pop_back()을 사용하였다.

 

// init

방향 결정을 위해서 'A'가 아닌 인덱스만 deque에 push

 

dq가 빌 때까지

{

    우 커서로 움직일 경우 거리(right)와 좌 커서로 움직일 경우 거리(left)와 비교하여 작은 값으로 움직인다.

    i값 갱신

    우 커서로 움직인다면 pop_front(), 좌 커서로 움직인다면 pop_back()

    움직인 거리만큼 answer에 추가

    상, 하 커서 움직임도 최소로 조작할 값으로 answer에 추가

}

 

 

#include <string>
#include <vector>
#include <deque>

using namespace std;

// 위: 다음, 아래: 이전
// 좌: 커서 왼쪽, 우: 커서 오른쪽

// name 길이 1 이상 20 이하

int solution(string name) {
    int answer = 0;
    
    // init
    deque<int> dq;      // for. 방향 결정
    for(int i=0; i<name.length(); i++){
        if(name[i]=='A') continue;
        dq.push_back(i);     // 'A'가 아닌 인덱스만
    }
    
    // process
    int i=0;    // start
    while(!dq.empty()){
        int right = i>dq.front() ? 
            dq.front()+name.length()-i : dq.front()-i;
        int left = i>dq.back() ? 
            i-dq.back() : i-dq.back()+name.length();
        
        if(right <= left){      // 오른쪽이 더 가깝다
            answer += right;    // 우 커서
            i = dq.front();
            dq.pop_front();
        }
        else{                   // 왼쪽이 더 가깝다
            answer += left;     // 좌 커서
            i = dq.back();
            dq.pop_back();
        }
        answer += min(name[i]-'A', 'Z'-name[i]+1);      // 상, 하 커서 움직임
    }
    
    return answer;      // 조이스틱 조작 횟수 최솟값 리턴
}