[PS] 조이스틱

문제

프로그래머스

원하는 알파벳을 만들기 위한 조이스틱의 조작 횟수 최솟값 구하기

 

풀이

이 문제의 핵심은 크게 두 가지이다.

1. 상하 조작 - 아스키코드를 통해 'A'로 시작하는 알파벳의 조작 횟수의 최솟값 구하기
2. 좌우 조작 - 현재 알파벳에서 다음 조작이 필요한 알파벳까지 가는 조작 횟수(거리)의 최솟값 구하기

 

1. 상하 조작 - 아스키코드

원하는 알파벳을 만들기 위한 조이스틱의 조작 횟수를 구해야 한다.

이때, 조작 횟수는 알파벳 간의 차이를 의미하므로 아스키코드로 구할 수 있다.

 

다만 무조건 A -> B로 가는게 아닌, A -> Z 로 갈 수도 있음에 주의한다.

X의 경우에는 A -> B 로 가는 상측 조작보다 A -> Z 로 가는 하측 조작이 더 적은 조작 횟수를 갖는다.

따라서 아래와 같이 둘 방법 중 최솟값을 구하는 방식으로 구현했다.

for (char c : name) {
    answer += min(c - 'A', 'Z' - c + 1);
}

 

2. 좌우 조작 - 거리의 최솟값

좌우 조작은 두 가지를 고려해야 한다.

조작이 필요한 알파벳의 위치를 구해서, 해당 위치까지 가기 위한 좌우 조작의 최솟값을 구한다.

 

2-1. 조작이 필요한 알파벳의 위치 구하기

현재 커서의 위치가 i에서 시작한다고 했을 때,

(1) 마지막 string이 아니고 (2) A가 아닌 알파벳이 i의 다음으로 조작이 필요한 알파벳이다.

다음으로 조작이 필요한 알파벳의 위치를 next라고 하겠다.

 

2-2. 해당 위치까지 가기 위한 좌우 조작 최솟값 구하기

좌우 조작 또한 상하 조작과 마찬가지로, 두 방법 중 최솟값을 구해야 한다.

 

계속 우측 조작을 하는 것이 최솟값을 가질지,

또는 우측 조작을 하다가 좌측 조작을 하는 것이 최솟값을 가질지,

또는 좌측 조작을 하다가 우측 조작을 하는 것이 최솟값을 가질지 고려한다.

 

여기서 계속 우측 조작을 하는 횟수는 간단하게 name.size()- 1로 구할 수 있다.

1. [우측 -> 좌측] 0에서 i까지 오른쪽으로 갔다가 다시 i만큼 왼쪽으로 되돌아가고, size-next만큼 왼쪽으로 이동
2. [좌측 -> 우측] 0에서 size-next만큼 왼쪽으로 갔다가 다시 size-next만큼 오른쪽으로 되돌아가고, i만큼 오른쪽으로 이동

 

아래와 같이 min()을 통해 이 세 가지 횟수 중 가장 작은 값을 가지는 move를 구하도록 구현했다.

    int move = size - 1; // 기본 우측 이동 시의 최대 이동 횟수
    for (int i = 0; i < size; ++i){
        int next = i + 1; // 다음에 방문할 인덱스
        
        // 다음 목표 찾기
        // A라면 상하 조작이 필요 없으므로 건너뛰기
        while (next < size && name[next] == 'A')
            ++next;
        
        // 오른쪽 i + 왼쪽 i (되돌아오기) + 왼쪽 (n - next)
        int path1 = 2 * i + (size - next);
        
        // 왼쪽 (n - next) + 오른쪽 (n - next) + 오른쪽 (i) 
        int path2 = i + 2 * (size - next);
        
        move = min ({move, path1, path2});
    }

 

코드

#include <string>
#include <vector>
#include <algorithm>

using namespace std;

int solution(string name) {
    int answer = 0;
    int size = name.size();
    
    // 1. 상하 조작
    for (char c : name) {
        answer += min(c - 'A', 'Z' - c + 1);
    }
    
    // 2. 좌우 조작
    int move = size - 1;
    for (int i = 0; i < size; ++i){
        int next = i + 1; // 다음에 방문할 인덱스
        
        // 다음 목표 찾기
        while (next < size && name[next] == 'A')
            ++next;
        
        // 오른쪽 i + 왼쪽 i (되돌아오기) + 왼쪽 (n - next)
        int path1 = 2 * i + (size - next);
        
        // 왼쪽 (n - next) + 오른쪽 (n - next) + 오른쪽 (i) 
        int path2 = i + 2 * (size - next);
        
        move = min ({move, path1, path2});
    }
    
    return answer + move;
}

 

회고

언뜻 보면 아스키코드만 생각하면 풀 수 있는 문제 같지만, 아니었다..

풀이 방법은 알겠는데 좌우 조작을 어떻게 구현해야 할지 고민하느라 많은 시간을 들였다.

 

좌 우 좌 우 번갈아가면서 이동해야 하기 때문에 많은 경우를 고려해야 한다고 생각했는데,

알고보니 전환점은 단 한번만 있으면 됐다.

오래 고민하지 말고 직접 돌려볼 걸 그랬다.