프로그래머스 - 마법의 엘리베이터 (Java)

 

문제 개요

 

마법의 세계에 사는 민수는 아주 높은 탑에 살고 있습니다. 탑이 너무 높아서 걸어 다니기 힘든 민수는 마법의 엘리베이터를 만들었습니다. 마법의 엘리베이터의 버튼은 특별합니다. 마법의 엘리베이터에는 -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	result
16	6
2554	16

 

---

 

풀이

 

이 문제를 풀기 위한 여러 방법이 있겠지만, 내 생각에는 그리디 알고리즘으로 푸는게 맞는 것 같다.

문제 본문에 중요한 부분에 표시해둔 내용을 요약하자면, 

• 민수는 탑의 n 층에 있고, 엘리베이터도 n 층에 있다.
• 민수는 0층으로 이동해야 한다.
• 엘리베이터의 버튼을 누르면 이동은 하는데, 각 버튼에는 10의 k승의 숫자만 적혀있다. (음수 포함)
• 엘리베이터의 버튼을 누르면 현재 층에서 해당 버튼에 적힌 숫자를 더한 층으로 이동한다.
• 만약 음수가 적혀있는 버튼을 눌렀는데, 현재 층에 그 숫자를 더했을 때 음수라면 엘리베이터는 움직이지 않는다.
  • 이런 경우가 나오면 안된다는 의미 같다.

 

맨 처음에는 입력받은 정수형 변수 storey의 각 자리의 수를 더하면 끝 아닌가?라는 생각을 했다.

 

그런데 이런 생각은 문제 본문을 제대로 읽지 않았기 때문에 생긴 오류였다. 

16층에서 0층으로 이동하는 방법을 서술했을 때, 분명 -1 버튼을 6회 누르고 -10 버튼을 1회 눌러서 돌 7개를 사용하는 방법도 존재한다.

하지만 문제에서 설명한 대로  +1 버튼을 4회 누르고 -10 버튼을 2회 눌러서 총 돌 6개를 사용하는 것이 돌을 더 적게 사용하는 방법이다. (이렇게 해도 중간에 계산 값이 0보다 작아지는 경우는 존재하지 않는다.)

 

그러면 이런 식으로 생각을 바꿀 수 있다.

 

입력받은 층수의 가장 큰 단위의 숫자부터 시작해서 그 값이 5 초과/미만 인지 체크하고, 만약 5를 넘는다면 10이 될 때까지 1을 더하고 10이 되었을 때 10을 빼주면 된다.

 

그런데 이 경우에도 오류가 존재한다.

 

나는 이 반례를 찾기가 좀 어려웠는데 만약에 민수가 456층에 있었다고 했을 때 제일 큰 단위의 수부터 체크해야 한다면 아래의 과정으로 진행이 될 것이다.

1. 백의 자리 숫자인 4부터 체크하면 4는 5보다 작기 때문에 1씩 감소하며 0이 되었을 때는 마법의 돌을 4회 사용한 것이 된다.
2. 십의 자리 숫자인 5는 위로 올리면 0이 아닌 10이 되어 돌을 1회 더 사용해야 하기 때문에 1씩 감소시켜 돌을 5회 사용한다.
3. 일의 자리 숫자인 6은 5보다 크기 때문에 1씩 4회를 더하고 10을 빼줘야 하기 때문에 추가적으로 돌을 1회 더 사용해서 총 5회 사용한다.

그러면 총 4 + 5 + 5 == 14회 사용한 것이 된다.

 

그런데 만약 작은 단위의 숫자부터 체크하면 이런 순서로 구할 수 있다.

1. 일의 자리 숫자인 6은 5보다 크기 때문에 1씩 4회 더하여 10을 채운다.
2. 십의 자리 숫자는 5이지만, 일의 자리에서 10을 채웠기 때문에 5에 1을 더해서 6이 되고, 6은 5보다 크기 때문에 1씩 4회 더해서 10을 채운다.
3. 백의자리 숫자는 4이지만, 십의 자리에서 10을 채웠기 때문에 4에 1을 더해서 5가 되고, 만약 10을 채우면 마법의 돌을 추가로 1회 더 사용해야 하므로 1씩 다섯 번 감소시켜 마법의 돌을 5회 사용하게 된다.

그러면 총 4 + 4 + 5 == 13회 사용한 것이 된다.

 

즉, n번째 자리에 위치한 숫자를 처리하는 과정에서 n-1번째에 위치한 숫자에 영향을 준다는 것이다.

때문에 가장 작은 자리의 숫자부터 체크하는 것이 맞고 효율을 따졌을 때 만약 n번째 숫자가 4 이하라면 당연히 1씩 감소시키는 게 맞고, 6 이상이라면 1씩 증가시키는 게 맞다. 

 

그런데 만약 n번째 자리의 숫자가 5라면?

 

나처럼 좀 애매하게 느낀 사람도 있을 것 같다. 아래의 경우의 수를 보자.

• 5를 올림처리 하는 경우
  • 45 == [4, 5] -> 일의 자리에서 5회, 십의 자리에서 5회, 백의 자리에서 1회 사용 == 총 11회
  • 55 == [5, 5] -> 일의 자리에서 5회, 십의 자리에서 4회, 백의 자리에서 1회 사용 == 총 10회
  • 65 == [6, 5] -> 일의 자리에서 5회, 십의 자리에서 3회, 백의 자리에서 1회 사용 == 총 9회
• 5를 내림처리 하는 경우
  • 45 == [4, 5] -> 일의 자리에서 5회, 십의 자리에서 4회 사용 == 총 9회
  • 55 == [5, 5] -> 일의 자리에서 5회, 십의 자리에서 5회 사용 == 총 10회
  • 65 == [6, 5] -> 일의 자리에서 5회, 십의 자리에서 4회, 백의 자리에서 1회 사용 == 총 10회

이 결과를 보면 5를 무작정 올려서 처리하거나 무작정 내려서 처리하는 것은 정답이 아니라는 것을 알 수 있다.

 

그래서 최종적으로 '만약 n번째 숫자가 5라면 n-1번째의 숫자까지 고려해서 n-1번째 숫자가 5 이하라면 n번째를 내림처리하고 그 반대라면 올림처리 하면 되나?'라는 생각에 도달할 수 있었다.

 

이런 조건을 추가해서 아까의 45, 55, 65를 다시 생각해 본다면,

• 45 == [4, 5] -> 일의 자리 숫자인 5를 판별하기 위해 십의 자리 숫자를 봤는데 4이기 때문에 내림처리해서 마법의 돌을 각각 5회, 4회로 총 9회 사용
• 55 == [5, 5] -> 일의 자리 숫자인 5를 판별하기 위해 십의 자리 숫자를 봤는데 5로 5 이하이기 때문에 내림처리하여 각각 5회, 5회로 총 10회 사용
  • 근데 이런 경우는 올림처리를 하더라도 일의 자리에서 5회, 십의 자리가 6이 되므로 십의 자리에서 4회, 백의 자리에서 1회로 총 10회가 되고, 결국은 올림처리를 하던지 내림처리를 하던지 같은 결과를 얻게 된다.
• 65 == [6, 5] -> 일의 자리 숫자인 5를 판별하기 위해 십의 자리 숫자를 봤는데 6으로 5 초과이기 때문에 올림처리하여 각각 5회, 4회로 총 9회 사용

 

첫 번째 예시에서 얻은 값들의 최소 값들만 추출된 것을 확인할 수 있었다! 그래서 이렇게 코드를 작성해 봤다.

 

---

 

코드

 

class Solution {
    public int solution(int storey) {
        int answer = 0;

        while(storey != 0) {
            int now = storey % 10;
            storey = storey / 10;
            int next = storey % 10;

            if (now > 5) {
                answer += 10 - now;
                storey++;
            } else if (now < 5) {
                answer += now;
            } else {
                if (next > 4) {
                    answer += 10 - now;
                    storey++;
                } else {
                    answer += now;
                }
            }
        }

        return answer;
    }
}

 

---

 

제출 결과

 

 

테스트도 잘 되네요 ㅎㅎ

 

내가 인텔리제이 IDE를 사용해서 작성한 마법의 엘리베이터 코드는 깃허브(여기링크)에 있습니다!

 

혹시 내용에 틀린점이 있거나 오류가 있다면 댓글로 알려주시면 감사하겠습니다!