LeetCode - 1974. Minimum Time to Type Word Using Special Typewriter

Solution

var minTimeToType = function(word) {
    let sec = 0
    let cur = 97

    for(char of word) {
        const code = char.charCodeAt()
        const diff = Math.abs(code - cur)

        sec += (diff <= 13 ? diff : 26 - diff) + 1
        cur = code
    }

    return sec
};

Explanation

이 문제는 탐욕 알고리즘을 이용해서 풀어보았다.

특정 알파벳으로 가는 방법은 시계방향으로 가는것과 반시계방향으로 가는것 두 가지만 존재한다. 위 두 방법 중 시간이 짧은, 즉 거리가 짧은 방법이 최적의 해답이된다.
이러한 지역적인 최적의 해답들이 모여 쌓인 최종 결과가 전역적인 최적의 해답이 되게 된다.

어느 방향으로 가는 것이 짧은지를 판단하기 위해서 charCodeAt 메소드를 사용했다.
a부터 z까지는 97 ~ 122의 유니코드를 갖는다.
현재 알파벳에서 특정 알파벳까지의 거리는 유니코드의 차의 절댓값으로 표현할 수 있다.

처음은 무조건 a부터 시작하기에 현재 알파벳을 나타내는 cur에 97를 할당한다.
목표 알파벳과 cur의 거리(유니코드의 차의 절댓값)이

• 13 이하면 그대로 반시계방향으로 가는것이 빠르기 때문에 절댓값이 거리가 된다.
• 13 초과면 반대로(시계방향)으로 돌리는 것이 빠르기 때문에 26-절댓값이 거리가 된다.

해당 알파벳에 도착하면 타이핑을 하는 시간(1초)가 필요하기 때문에 1 또한 더해준다.
이동을 완료한 후 마지막으로 cur에 현재 위치한 알파벳을 재할당해준다.
이 과정을 for문을 통해 반복시켜주면된다.