프로그래머스 - 조이스틱

programmers.co.kr/learn/courses/30/lessons/42860#

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

 

1. 입력 글자 길이 n 만큼의 크기의 문자열을 전부 'A' 가 들어가게 생성한다

2. 입력 글자와 'A' 로 만 구성된 글자가 같을 때 까지 다음의 반복문을 돌린다

   - 1) 문자 변경

   : 문자 변경시에 이동 횟수를 최소화 해야하므로

     현재 알파벳 - 'A' 의 거리(up_len, 조이스틱 윗쪽 방향), 'Z' + 1 - 현재 알파벳 의 거리 (down_len, 조이스틱 아랫방향) 중 작은 값을 찾는다

     그 작은값을 answer 에 추가해주고, 해당 커서의 문자를 바꾼다

 

   - 2) 커서 이동

   : 좌측 이동 과 우측 이동을 나눠서 하며, 이동하면서 커서를 옮길때 마다 카운팅 하고, 커서를 옮긴 지점의 글자가 다르면 이동을 멈춘다

     그리고 둘 중 더 적게 이동한 쪽을 채택해서 answer 에 더한다.

 

 

- c++

 

#include <bits/stdc++.h>
 
using namespace std;
 
int solution(string name) {
    int answer = 0, len = name.length(), cursor = 0;
    string init_str(len, 'A');
    
    while(1) {
        if (init_str[cursor] != name[cursor]) {
            int up_len = name[cursor] - 'A', down_len = 'Z' + 1 - name[cursor], min_num;
            min_num = min(up_len, down_len);
            answer += min_num;
            init_str[cursor] = name[cursor];
        }
        
        if (init_str == name) break;
        
        int left_len = 0, right_len = 0, left_idx = cursor, right_idx = cursor;
        // move left
        while(1) {
            left_idx--;
            left_len++;
            if (left_idx < 0) left_idx = len - 1;
            if (init_str[left_idx] != name[left_idx]) break;
        }
        
        // move right
        while(1) {
            right_idx++;
            right_len++;
            if (right_idx >= len) right_idx = 0;
            if (init_str[right_idx] != name[right_idx]) break;
        }
        
        if (left_len >= right_len) {
            cursor = right_idx;
            answer += right_len;
        } else if (left_len < right_len) {
            cursor = left_idx;
            answer += left_len;
        } 
    }
    
    return answer;
}