[프로그래머스 Lv2] : 조이스틱

문제 링크

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

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

원하는 이름을 완성하기 위해서 조이스틱을 최소한 몇 번 조작해야하는 지 리턴하는 문제.

 

풀이

 이번 문제가 여태까지 풀어본 2단계 문제중에 제일 어려운 것 같다.

내 방식대로 몇 번을 시도해봤지만 몇 개의 케이스에서 계속 실패해서, 결국 구글 선생님들께 가르침을 받았다.

초기에 이름은 'A' 로만 이루어져있으며 조이스틱을 상하좌우로 움직여서 원하는 이름을 완성해야한다.

조이스틱의 조작은 아래와 같다.

▲ - 다음 알파벳
▼ - 이전 알파벳 (A에서 아래쪽으로 이동하면 Z로)
◀ - 커서를 왼쪽으로 이동 (첫 번째 위치에서 왼쪽으로 이동하면 마지막 문자에 커서)
▶ - 커서를 오른쪽으로 이동 (마지막 위치에서 오른쪽으로 이동하면 첫 번째 문자에 커서)

 

 먼저 조이스틱을 위 또는 아래로 조작할 때, 최소한의 횟수로 조작하는 방법을 살펴보자.

만약 'A'를 'C'로 만들고 싶다고 하자. 이때 조이스틱을 위로 2번 조작해서 C로 만들 수도 있지만,

아래로 24번 조작해서 C를 만들 수도 있다.( A -> Z -> Y -> X -> ... -> C 순)

문자 끼리도 +, - 연산이 가능하다. 아스키 코드로 바뀌어서 계산된다.

따라서 'C' - 'A' 를 하면 아스키코드 상 2가 차이나기 때문에 2가 리턴된다.

원하는 알파벳을 만드는 경우는 2가지가 있다.

1. (원하는 알파벳 - 'A') 를 한 횟수만큼 조이스틱을 위로 조작한다.

2. (26 - (원하는 알파벳 - 'A')) 를 한 횟수만큼 조이스틱을 아래로 조작한다.

이때 26에서 빼주는 이유는 알파벳의 총 개수가 26개이기 떄문에.

 

위 또는 아래로 조작하는 경우는 그렇게 어렵지 않다. 하지만 문제는 좌우로 조작하는 경우였다.

커서를 알파벳을 변경하고 싶은 칸으로 이동하기 위해서는 왼쪽 또는 오른쪽으로 조이스틱을 조작해야한다.

이때 조이스틱 조작횟수가 최소가 되도록하려면 어떻게 해야할까?

연속된 A의 앞뒤를 각각 i와 ind라고 했을 때,

좌우 총 이동횟수의 최소값을 위와 같이 정의할 수 있다. (구글에서 참고한 아이디어)

answer = (각 자리마다 상하 조작 횟수 + 좌우 최소 이동횟수 합) 이 된다.

 

코드 작성

#include <string>
#include <vector>
#include <math.h>
#include <algorithm>
#include <iostream>
using namespace std;
 
int solution(string name) {
    int answer = 0;
    int left_right = name.length() - 1;
    
    for(int i = 0; i<name.length(); i++){
        answer += min(name[i] - 'A', 26 - (name[i] - 'A'));
        int end = i + 1;
        while(end < name.length() && name[end] == 'A')
            end++;
        left_right = min(left_right, i + (int)name.length() - end + min(i, (int)name.length() - end));
    }
    answer += left_right;
    return answer;
}

 

보고 이해하려고 해도 어려운 이런 아이디어를 생각해내시는 분들은 천재인듯 하다.

코딩테스트의 길은 멀고도 험하다...