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

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

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

 레벨 2라고 되어있지만 체감은 훨씬 어려웠던 문제.

 

 문자를 조이스틱의 최소한의 움직임으로 출력하라는 문제를 읽고 막막했다. 조이스틱이 움직이는 걸 일일이 세는 것도 생각해야 하는데, 최소한의 움직임까지 고려하라니. 일단 간단한 사례를 직접 실행해보고 문제를 풀려고 하는 편이라 머리가 아팠다. 갓글 검색 덕분에 아이디어를 얻었다.

 그 중에 A에서 출발할지 Z에서 출발할지 min을 사용하여 답을 얻어내는 방식이 간단하고 신선했다. Z에서 출발할 경우 A에서 Z로 한 번 이동하므로 +1을 해준다.

 그 다음 알파벳이 A일 경우에 조이스틱을 위아래로 조작할 필요가 없으므로 좌측으로 이동해준다.

 아직 min_way 값을 완전히 이해하지 못했는데, 내가 이해한 바가 맞는지 모르겠다.

min_way는 역방향으로 이동해 Z에서 도착지까지 가는게 빠른지, 정방향으로 이동하는게 빠른지, 아니면 기존에 있던 방향을 고수하는게 나을지 3가지 값을 비교하여 가장 짧은 값을 도출해넨다. 그것까진 알겠는데 모든 알파벳을 순회하면서 이 값을 비교한다는게 어떤 의미인지 직접 시물레이션 해봐야할 것 같다.

 

int solution(string name) {
    int answer = 0;
    int size = name.size();
    int min_way=size-1;
    
    for(int i=0; i< size; ++i ){
        answer += min(name[i]-'A', 'Z'-name[i]+1);
        int idx=i+1;
        while(idx<size && name[idx]=='A'){ idx++; }
        min_way = min(min_way, min(size-idx+i*2, (size-idx)*2+i) );
    }
    answer += min_way;
    return answer;
}

처음 어떻게 풀지 막막해서 일단 세고 보았다.

첫 번째0은 0이고 두 번째 0은 10이다.

a b c d e f  g h i  j k  l m n o p q r  s t u v w x y z 0 1 2 3 4 5 6 7 8 9 0 1 2  3 4 5 6 7 8 9 0 1 2 3 4 5     ^                                                                        10      13

1은 뒤에서 부터 시작되고 뒤에서 부터 첫 번째0이 10이다.

 

a b c d e f   g h i  j k  l m n o p q r  s t u v w x y z            0 5 4 3 2 1  0 9 8 7 6 5 4  3 2 1 0 9 8 7 6 5 4 3 2 1                   ^                                                                                   13    10

n을 기준으로 앞으로 가나 뒤로 가나 이동 횟수가 같아진다. 여기까지만 풀고 어떻게 풀지 막막해서 다른 풀이를 찾아보았다.