C++로 문자열 출력에 필요한 로터리 다이얼의 총 회전 수 구하기

문제 개요

모든 소문자 영어 알파벳이 적혀 있는 로터리 다이얼(rotary dial)이 하나 있다고 가정해 봅시다. 다이얼에는 프린터가 연결되어 있으며, 포인터가 가리키는 문자가 3초 동안 유지되면 해당 문자가 종이에 출력됩니다.

다이얼은 처음에 'a'에 위치해 있고, 문자를 출력한 뒤에도 초기 위치로 되돌아가지 않습니다. 즉, 다이얼은 마지막으로 가리킨 문자에서부터 계속 움직입니다. 우리에게 문자열 s가 주어지며, 이 문자열을 순서대로 출력해야 합니다. 다이얼을 다른 글자로 이동시킬 때마다 그 이동 거리만큼 회전이 발생합니다. 목표는 주어진 문자열 s를 완성하기 위해 필요한 총 회전 수를 구하는 것입니다.

예를 들어 입력이 s = "elephant"이라면, 출력은 63이 됩니다.

풀이 접근 방식

다이얼은 원형으로 배치되어 있기 때문에 두 문자 사이의 거리는 두 가지 방향(시계 방향 또는 반시계 방향) 중 더 짧은 쪽을 선택해야 합니다. 알파벳은 총 26글자이므로, 두 문자 간 차이의 절댓값과 그 보수(26에서 뺀 값) 중 최솟값을 매번 더해주면 됩니다.

구체적인 단계는 다음과 같습니다.

현재 위치 t를 'a'로 초기화하고, 누적 결과 res를 0으로 설정합니다.
문자열의 각 문자 s[i]에 대해 |t - s[i]|와 26 - |t - s[i]| 중 작은 값을 res에 더합니다.
현재 위치 t를 s[i]로 갱신한 후 다음 문자로 넘어갑니다.
모든 문자를 처리한 뒤 res를 반환합니다.

t := 'a'
res := 0
for initialize i := 0, when i < size of s, update (increase i by 1),
do:
    res := res + minimum of (|t - s[i]|, 26 - |t - s[i]|)
    t := s[i]
return res

C++ 구현 예제

아래 코드를 통해 실제 동작을 확인해 보겠습니다.

#include <bits/stdc++.h>
using namespace std;
#define N 100
int solve(string s) {
    char t = 'a';
    int res = 0;
    for(int i = 0; i < s.size(); i++){
        res += min(abs(t - s[i]), 26 - abs(t - s[i]));
        t = s[i];
    }
    return res;
}
int main() {
    string s = "elephant";
    cout<< solve(s);
    return 0;
}

입력

"elephant"

출력

동작 원리 살펴보기

"elephant"의 경우를 단계별로 계산해 보면 다음과 같습니다.

'a' → 'e': 거리 4
'e' → 'l': 거리 7
'l' → 'e': 거리 7
'e' → 'p': 거리 11
'p' → 'h': 거리 8
'h' → 'a': 거리 7
'a' → 'n': 거리 13
'n' → 't': 거리 6

이 값들을 모두 더하면 4 + 7 + 7 + 11 + 8 + 7 + 13 + 6 = 63이 되어 기대한 결과와 일치합니다. 이 알고리즘의 시간 복잡도는 문자열 길이에 비례하는 O(n)으로 매우 효율적입니다.