[프로그래머스 Level.2] 마법의 엘리베이터 (연습문제) (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 함수를 완성하세요.

 

---

제한사항

• 1 ≤ storey ≤ 100,000,000

 

---

 

입출력 예

storey	result
16	6
2554	16

 

---

 

입출력 예 설명

 

입출력 예 #1

• 문제 예시와 같습니다.

 

입출력 예 #2

• -1, +100이 적힌 버튼을 4번, +10이 적힌 버튼을 5번, -1000이 적힌 버튼을 3번 누르면 0층에 도착 할 수 있습니다. 그러므로 16을 return 합니다.

 

 

 

나의 코드

class Solution {
    // 처음에는 (1. 6이상인 경우 2. 5이하인 경우) 두 구간으로 나눠서 품-> X 
    // 두번째는 (1. 6이상인 경우 2. 5이상이면서 앞자리가 5이상인 경우 3. 5이하인 경우) 세 구간으로 나눠서 품 -> O
    public int solution(int storey) {
        int answer = 0;
        
        while(storey != 0) {
            int rest = storey % 10;
            
            if(rest >= 6) {
                storey += 10 - rest;
                answer += 10 - rest;
            } else if(rest >= 5 && (storey % 100) / 10 >= 5) {
                storey += 10 - rest;
                answer += 10 - rest;
            } else if(rest <= 5) {
                storey -= rest;
                answer += rest;
            }
            
            storey /= 10;
        }
        
        return answer;
    }
}

 

풀이

1. 처음에는 층을 나타내는 storey의 1의 자리 숫자 rest가 6 이상일 때와 5 이하일 때만 따져서 6 이상인 경우에는 (10 - rest)만큼 올라가서 1의 자리 숫자가 0이 되도록 하고 5 이하인 경우에는 rest만큼 내려가서 1의 자리 숫자가 0이 되도록 하였다.  그러나 만약 1의 자리 숫자가 5일 때 10의 자리 숫자가 5 이상이라면 올라가는 것이 더 빠르다. 정확히 따지면 55처럼 1의 자리 숫자가 5이고 10의 자리 숫자가 5일 때는 올라가든(5 + 4 + 1) 내려가든(5 + 5) 똑같지만 1의 자리 숫자가 5이고 10의 자리 숫자가 6 이상일 때는 올라가는 것이 더 빠르다.
2. 자세히 예를 들어보자.
   
   45인 경우 : 1의 자리 숫자가 5, 10의 자리 숫자가 5 이므로 내려가는 것이 더 빠르다.
   올라가는 경우 5층을 올라가서 50이 되고 여기서 10층씩 5번을 내려오면 총 10번이 걸리고 50에서 10층씩 5번을 올라가고 100층씩 1번을 내려오면 총 11번이 걸린다.
   내려가는 경우 5층을 내려가서 40이 되고 여기서 10층씩 4번을 내려오면 총 9번이 걸린다.
   
   55인 경우 : 1의 자리 숫자가 5, 10의 자리 숫자가 5 이므로 올라가든 내려가든 똑같다.
   올라가는 경우 5층을 올라가서 60이 되고 여기서 10층씩 4번을 올라가서 100층이 되고 100층씩 1번을 내려오면 0층이 되므로 총 10번이 걸린다.
   내려 가는 경우 5층을 내려가서 50이 되고 여기서 10층씩 5번을 내려가서 0층이 되면 총 10번이 걸린다.
   
   65인 경우 : 1의 자리 숫자가 5, 10의 자리 숫자가 6이므로 올라가는 것이 더 빠르다.
   올라가는 경우 5층을 올라가서 70이 되고 여기서 10층씩 3번을 올라가서 100층이 되고 100층씩 1번을 내려오면 0층이 되므로 총 9번이 걸린다.
   내려가는 경우 5층을 내려가서 60이 되고 10층씩 내려가면 6번이 걸려 총 11번이 되고 60에서 10층씩 4번 올라가고 100층씩 1번을 내려오면 총 10번이 걸린다.
   
   따라서 55인 경우는 어디에 양쪽 어디에도 포함해도 되지만 65부터는 올라가는 것이 더 빠르다는 것을 알아야 한다. 그러므로 1의 자리 숫자가 5이고 10의 자리 숫자가 (5 or 6) 이상인 경우에는 올라가는 것이 빠르다.
3. 이렇게 세 개의 구간으로 나눠 풀어야 한다는 것을 파악하고 총 세개의 구간으로 나누어 풀었다.
4. 우선 storey가 0이 될 때까지 while문을 반복 실행한다.
5. 1의 자리 숫자를 알아내기 위해 storey를 10으로 나눈 나머지를 이용해 구하고 rest에 저장하였다.
6. 그리고 이 rest를 통해 rest가 6 이상인 경우, 5 이상이며 10의 자리 수도 5이상인 경우, 5 이하인 경우로 나누었다.
7. 6 이상인 경우에는 (10 - rest)층을 올라가야 하므로 storey와 answer에 각각 (10 - rest)를 더해주었다.
8. sotrey를 100으로 나누고 이것을 다시 10으로 나누어 10의 자리 숫자만 구한다.
9. 그리고 1의 자리 숫자가 5 이상이고 10의 자리 숫자가 5 이상인 경우에도 (10 - rest)층을 올라가야 하므로 storey와 answer에 각각 (10 - rest)를 더해주었다.
10. 5 이하인 경우에는 내려가는 것이 더 빠르므로 rest만큼 내려가면 된다. 따라서 storey에는 rest만큼 빼주고 answer에는 rest만큼 더해주었다.
11. 그리고 나서 storey를 10으로 나누어 다음 10의 자리 숫자가 1의 자리 숫자가 되도록 하고 반복문을 진행하도록 한다.
12. 이렇게 반복문을 진행하여 storey가 0이 되면 while문을 빠져나오고 총 횟수를 카운팅한 answer를 반환한다.