[프로그래머스] 마법의 엘리베이터

https://school.programmers.co.kr/learn/courses/30/lessons/148653

프로그래머스

 마법의 엘리베이터는 0층 이상의 값을 가지며, 한번에 10^c (c >= 0) 층(1, 10, 100 ... 위 아래 다 가능)씩 움직일 수 있다. 한번 움직이는데 마법의 돌 하나가 필요할 때 최소 개수로 0층까지 이동하는 것이 이번 문제의 목표다.

• 1 <= 현재 층 수(storey) <= 100,000,000

 전체 층을 10의 자리 단위로 나눠서 생각하자. 이 경우 16층은 10층과 6층으로 나눠서 볼 수 있다. 이때 한번에 움직일 수 있는 층수는 정의에 의해 10의 C승 단위이므로 반복문과 몫, 나머지를 이용하면 일관된 방식으로 문제를 처리할 수 있다.

 예를 들어 storey = 555인 경우, 최소로 소모되는 돌의 개수는 14개이다. 555 -(5)> 560 -(4)> 600 -(4)> 1000 -(1)> 0이기 때문이다. 이때 매 순간마다 10^c 자리만 생각해보자. 각 자리에서 올림 등 로직을 전부 처리하고 나면 현재 자리의 값은 모두 처리한 상태이므로  10^c자리의 값은 10^c+1 자리의 계산에 영향을 주지 않는다. 

 위 예시에서 1의 자리에 있는 5는 올림으로 10의 자리를 6으로 만들었다. 이후 1의자리의 값은 10의 자리에 영향을 주지 않는다. 마찬가지로 10의 자리의 6은 올림을 통해 100의자리를 5으로 만든다. 이후 연산에 10의 자리는 영향을 주지 않는다. 이때 잘 생각해보면, 값을 60으로 처리하든 6으로 처리하든 사용하는 돌의 개수는 변하지 않는다. 따라서 반복문을 실행할 때마다 1의 자리에 집중하여 연산하기 위해 라운드마다 storey 값을 10으로 나누면 항상 1의 자리 값에 대해 연산할 수 있게 된다. 

값을 계산하는 모습. 검은 바는 이전 값에 관심 없음을 나타낸다.

 매 순간 1의 자리 값만 생각할 수 있다는 것은 알았으므로, 구체적으로 어떤 값을 가질 때 값을 올리고 내려야 하는지 생각해보자. 직관적으로 생각하면 6부터는 반드시 올리는 것이 더 좋다. 내리면 반드시 6개를, 올리면 10 - 6 [+ 1] 개를 소모하기 때문이다. 반대로 4 이하의 값은 반드시 내리는 것이 더 좋다. 내리면 반드시 4개를, 올리면 반드시 10 - 4 [+ 1]개를 소모하기 때문이다.

 따라서 4 이하 또는 6 이상인 경우는 확실하다. 반면 값이 5인 경우는 애매하다. 내리면 반드시 5개를 내지만, 올리면 5 [+ 1] 개를 내야 하기 때문이다. 직관적으로 따지면 각 순간에 내리면 5개, 올리면 5 [+ 1]의 돌을 써야 하기 때문에 내리는 것이 타당한 것처럼 생각되지만, 다음 자리의 값에 따라 5를 올리는게 더 좋을 수도 있다. 따라서 5인 경우에는 다음 자리의 값까지 고려해야 한다.

 그렇다면 다음 값이 얼마 이상일 때 5를 올리는 것이 더 좋을까? 기본적으로 올림은 다음 값에 + 1 처리하는 효과를 가지고 있다. 이때 값을 올려서 효용이 있는 범위는 5 이상으로, 5 + 1 = 6부터는 6 >= 10 - 6 [+ 1] + 1(올림)가 되어 올림의 가치가 있다. 따라서 현재 값이 5일 때 다음 값이 5 이상이면 올리더라도 이득이 된다.

 정리하면 다음과 같다.

1. 각 자리는 독립적으로 연산할 수 있으므로, 반복문을 순회할 때마다 1의 자리에 대한 연산으로 일반화하기 위해 기존 storey를 10으로 나눌 수 있다.
2. 값은 올리거나 내리는 조건은 다음과 같다.
   1. 4 이하이면 버린다. ( 4 < 6 [+ 1] )
   2. 6 이상이면 올린다. (6 > 4 [+ 1])
   3. 5의 경우 다음 숫자가 5 이상이면 올리는 것이 이득이다. (5 + 1 >= 4 [+1] + 1)

위 로직을 기반으로 코드를 작성하면 다음과 같다.

function solution(storey) {
    let count = 0;
    while (storey > 0) {
        let cur = storey % 10;
        storey = Math.trunc(storey / 10);
        
        if(cur > 5 || (cur === 5 && (storey % 10 >= 5))) {
            count += 10 - cur;
            storey += 1;
        } else {
            count += cur;
        }
    }
    return count;
}

while문을 순회하며 1의 자리의 값인 cur을  %10 연산으로 구하고, 다음 라운드를 위해 storey의 값을 10으로 나눈다. cur 값이 ① 5를 초과하거나 ② 5이면서 다음 값이 5 이상이라면 올리고, 아니면 내린다. 매 순간마다 올리고 내린 숫자를 다 더하면 사용한 돌의 수가 되므로 해당 값을 반환한다.

통과한 모습

 테스트 케이스는 전부 통과했다. 생각하지 못한 반례가 없다면 꽤 합리적인 풀이가 아닐까 생각한다. 다 풀고 나서 풀이를 보니까 문자열로 처리하는 케이스가 많았는데, 자바스크립트의 number 타입은 다른 언어의 double만큼의 숫자(IEEE 754 64비트 바이너리 정밀도)를 표현할 수 있어 정수만 따지면 조 단위의 숫자를 표현할 수 있다는 점, 현재 숫자의 범위가 기껏해야 1억이라는 점에 있어서 굳이 문자열로 바꿀 필요까지는 없다고 생각한다.