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

🔗 문제 링크: https://school.programmers.co.kr/learn/courses/30/lessons/148653

프로그래머스

 

🔍  해결 과정

유형: 그리디

시간복잡도: O(logN), N: storey

 

이 문제는 10의 제곱승의 절댓값을 활용하여 주어진 층수에서 0층으로 갈 때 활용할 수 있는 버튼의 최소 횟수를 구해야 합니다.

주어진 storey 매개변수에서 각 자리에 있는 값들을 0으로 만들도록 하는 것이 핵심이고 또한 최솟값의 횟수로 각 자리를 0으로 만들어주어야 합니다.

 

문제의 예시 2를 보면 각 자리의 값을 무조건 0으로 내리는 방식을 취하면 정답을 도출할 수 없다는 것을 알 수 있습니다.

그래서 0부터 10까지의 숫자를 나열한 다음 생각을 해보았습니다.

0   1   2   3   4   5   6   7   8   9  10

 

확실한 점은 4이하의 숫자는 무조건 내려주어야 하고, 6이상의 숫자는 무조건 10의 값으로 올려줘야 최솟값을 도출할 수 있습니다.

예를 들어서 17의 값을 볼 때 17 -> 18 -> 19 -> 20 -> 10 -> 0 의 과정으로 단 5회만에 0으로 만들어 줄 수 있고, 14의 경우는 14 -> 13 -> 12 -> 11 -> 10 -> 0 의 과정으로 최소 횟수 5회 만에 0으로 만들 수 있습니다.

하지만 5의 경우는 상황에 따라서 올려주어야 하는 상황이 있고, 내려주어야 하는 상황이 있습니다.

 

예를 들어서 555의 숫자가 있다고 가정한다면 다음과 같은 과정으로 최소 횟수를 도출할 수 있습니다.

1️⃣ 1의 자리 5의 값과 10의 자리 값을 살펴본다.
2️⃣ 이 때 10의 자리값을 살필 때 값이 5인 점이 확인되었다.
3️⃣ 1의 자리 값을 반올림하여 10의 자리값을 6으로 만들어준다.  (현재값: 560, 버튼 횟수: 5)
4️⃣ 10의 자릿수를 살필 때 6은 5보다 크므로 값 0으로 만들기 위해서는 40을 더해주어야 한다. (현재값: 600, 버튼 횟수: 9)
5️⃣ 100의 자리 값은 6이므로 마찬가지로 400을 더해준다. (현재값: 1000, 버튼 횟수: 13)
6️⃣ 마지막으로 1000의 자리값 1은 한번에 0을 만들 수 있으므로 1000의 값을 빼준다. (현재값: 0, 버튼 횟수: 14)

 

위와 같은 과정으로 최소 14번의 버튼을 눌러 0으로 만들 수 있습니다.

 

다시말해 현재 보고 있는 자릿수가 5라면 그 다음 자릿수의 값이 5이상이면 10으로 만들어주어야 하고, 그게 아니라면 내려주는 방식으로 설계를 해야 최소 횟수를 도출할 수 있습니다.

 

---

✏️ 코드

import java.util.*;

class Solution {
    
    public int solution(int storey) {
        int answer = 0;
        
        while (storey > 0) {
            int number = storey % 10;
            int nextNumber = (storey / 10) % 10;
            
            if (number > 5 || (number == 5 && nextNumber >= 5)) {
                answer += 10 - number;
                storey = storey / 10 + 1;
            } else {
                answer += number;
                storey /= 10;
            }
        }
        
        return answer;
    }
}