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

마법의 엘리베이터

문제 링크

마법의 엘리베이터

분석

마법의 엘리베이터에는 -1, +1, -10, +10, -100, +100 등 10의 배수로 이동합니다.
버튼을 한 번 누를 때마다 마법의 돌 1개가 소모됩니다.
storey를 0으로 만들기 위해 마법의 돌을 최소한으로 사용하는 경우의 수를 구해야합니다.

각 자릿수마다 올림, 내림을 결정해서 최소 비용을 찾는 문제입니다.
각 자리의 숫자를 기준으로 0~4는 내림, 6~9는 올림, 5는 상위 자리수를 고려해야합니다.

풀이

int solution(int storey) {
    int answer = 0;
    
    while(storey != 0)
    {
        // 1의 자리의 숫자 추출
        int digitNum = storey % 10;
        
        if (digitNum > 5)
        {
            // 올림하는 것이 최소 비용인 경우
            answer += 10 - digitNum; // 필요한 돌 수
            storey += 10; // 올림
        }
        else if (digitNum < 5)
        {
            // 내림하는 것이 최소 비용인 경우
            answer += digitNum; // 필요한 돌 수
        }
        else
        {
            // 5인 경우로 경우에 따라 올리거나 내림
            // 비용은 5로 같다.
            answer += 5;
            
            // 다음 자릿수를 확인한다.
            int nextNum = (storey / 10) % 10;
            if (nextNum >= 5)
            {
                // 다음 자릿수가 5이상이라면 올림을 하는 것이 최소 비용이다.
                storey += 10;
            }
        }
        
        // 1의 자릿수를 제거한다.
        storey /= 10;
    }
    
    return answer;
}

성능 요약

시간 복잡도는 $O(log_{10}(n))$입니다.

• 반복문 $O(log_{10}(n))$

공간 복잡도는 고정된 크기의 상수 공간을 사용하기 때문에 $O(1)$입니다.

테스트 1 〉 통과 (0.01ms, 3.59MB)
테스트 2 〉 통과 (0.01ms, 3.68MB)
테스트 3 〉 통과 (0.01ms, 4.14MB)
테스트 4 〉 통과 (0.01ms, 4.21MB)
테스트 5 〉 통과 (0.02ms, 3.68MB)
테스트 6 〉 통과 (0.01ms, 4.17MB)
테스트 7 〉 통과 (0.01ms, 4.2MB)
테스트 8 〉 통과 (0.01ms, 4.15MB)
테스트 9 〉 통과 (0.01ms, 4.17MB)
테스트 10 〉 통과 (0.01ms, 4.14MB)
테스트 11 〉 통과 (0.01ms, 4.14MB)
테스트 12 〉 통과 (0.01ms, 4.19MB)
테스트 13 〉 통과 (0.01ms, 4.14MB)