[프로그래머스] 마법의 엘리베이터 Lv2 JAVA [그리디][엄탱]

문제 링크

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

프로그래머스

문제 설명

마법의 세계에 사는 민수는 아주 높은 탑에 살고 있습니다. 탑이 너무 높아서 걸어 다니기 힘든 민수는 마법의 엘리베이터를 만들었습니다. 마법의 엘리베이터의 버튼은 특별합니다. 마법의 엘리베이터에는 -1, +1, -10, +10, -100, +100 등과 같이 절댓값이 10c (c ≥ 0 인 정수) 형태인 정수들이 적힌 버튼이 있습니다. 마법의 엘리베이터의 버튼을 누르면 현재 층 수에 버튼에 적혀 있는 값을 더한 층으로 이동하게 됩니다. 단, 엘리베이터가 위치해 있는 층과 버튼의 값을 더한 결과가 0보다 작으면 엘리베이터는 움직이지 않습니다. 민수의 세계에서는 0층이 가장 아래층이며 엘리베이터는 현재 민수가 있는 층에 있습니다.

마법의 엘리베이터를 움직이기 위해서 버튼 한 번당 마법의 돌 한 개를 사용하게 됩니다. 예를 들어, 16층에 있는 민수가 0층으로 가려면 -1이 적힌 버튼을 6번, -10이 적힌 버튼을 1번 눌러 마법의 돌 7개를 소모하여 0층으로 갈 수 있습니다. 하지만, +1이 적힌 버튼을 4번, -10이 적힌 버튼 2번을 누르면 마법의 돌 6개를 소모하여 0층으로 갈 수 있습니다.

마법의 돌을 아끼기 위해 민수는 항상 최소한의 버튼을 눌러서 이동하려고 합니다. 민수가 어떤 층에서 엘리베이터를 타고 0층으로 내려가는데 필요한 마법의 돌의 최소 개수를 알고 싶습니다. 민수와 마법의 엘리베이터가 있는 층을 나타내는 정수 storey 가 주어졌을 때, 0층으로 가기 위해 필요한 마법의 돌의 최소값을 return 하도록 solution 함수를 완성하세요.

해설

해당 문제는 그리디 문제로 풀 수 있다.

그리디 문제는 순서대로 현재 값을 해결해 나가면서 앞으로 나아가는 문제이다.

즉, 주어진 storey 층을 1의 자리부터 가장 끝 자리까지 한자리 한자리 해결해 나가면 된다.

 

이 문제는 두가지 정도 알면 좋다.

 

1. 기준 정하기, 5보다 큰지 작은지 같은지 나누면 된다.

2. 해당 숫자가 5라면, 앞자리가 5보다 같거나 큰지 아니면 작은지 나누면 된다.

 

우선, 문제를 이해해야 한다. 이 문제는 층수 누르는 것 을 최소로 하는 것이다.

그렇다면 숫자가 5보다 작으면 그냥 해당 숫자만큼 빼주고 0으로 만드는 게 최솟값이 되지만 5보다 큰 경우에는 더해줘서 앞자리 숫자를 +1 시켜주고 0으로 만드는게 최솟값이 된다.

예를 들어보면 3인 경우에 +7을 해서 10을 만들어서 해당 자릿수를 0으로 만드는 것보다, -3을 해서 0을 만드는 게 더 최솟값이 된다.

 

여기서 중요한 게 하나 더 있다 해당 숫자가 5라면 앞자리가 5보다 큰지 작은지 알아야 한다.

왜냐? 5를 0으로 만드는 최솟값은 -5 혹은 +5 즉, 5번이 마이너스든 플러스든 똑같기 때문이다. 그렇다면, +5를 해서 앞자리를 +1을 해야 할까? 아니면 -5를 해서 앞자리를 +0을 해줘야 하는 것일까?

그래서 앞자리를 생각해줘야 한다는 것이다. 앞자리가 5보다 작으면 앞자리를 +1을 해주면 앞자리에서 버튼을 누를 때 최솟값이 늘어나고, 앞자리가 5보다 큰 경우에는 +1을 해줘야 앞자리에서 최솟값이 감소한다.

코드

1. 일의 자리부터 끝 자리까지 for문으로 하지 말고 while문으로 하는 게 좋다. 이유는 storey의 맨 앞자리가 5보다 큰 경우에는 앞자리가 하나 더 생기기 때문에 for문으로 하면 복잡해지기 때문이다.

 

2. 더하기를 해줘서 앞자리를 증가시키는 경우에는 storey에 직접 앞자리에 +1을 해주면 좀 더 편해진다.

이 부분은 직접 자신이 구현해 보면 이해될 것이다.

 

class Solution {
    public int solution(int storey) {
        int answer = 0;
        
        while(storey > 0) {
            int num = storey % 10;
            storey /= 10;
            
            if (num > 5) {
                answer += 10 - num;
                storey++;
                
            } else if (num < 5) {
                answer += num;
            } else if (storey % 10 >= 5) {
                answer += 5;
                storey++;
                
            } else {
                answer += 5;
            }
        } 
        
        return answer;
    }
}