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

문제

코딩테스트 연습 - 마법의 엘리베이터 | 프로그래머스 스쿨 (programmers.co.kr)

프로그래머스

민수와 마법의 엘리베이터가 있는 층을 나타내는 정수 storey 가 주어졌을 때, 0층으로 가기 위해 필요한 마법의 돌의 최소값을 return 하시오.

 

알아야 할 개념

• 재귀 함수 호출

풀이

풀이는 다음과 같다. 

1. 숫자 < 10 이하일때 버튼 누를 개수를 배열에다 저장
2. 현재 숫자에서 5 이하이면, 값만 더해주고 재귀호출
3. 현재 숫자에서 5 이상이면, 다음 숫자에 + 1을 한다음 재귀호출
4. 현재 숫자 < 10 이면, answer 업데이트 후 종료

 

다음과 같은 포맷으로 브루트 포스를 할 것이다. 

while( num > 10){
	...
    ...
    num /= 10
}

문제 조건 최대 범위가 100,000,000 임으로재귀 호출 최대 단계는 10단계가 된다. 

각 재귀 호출에선 최대 2번씩 호출된다.( 5 이하, 5이상 ) 

• 눌러야 할 버튼이 [ 0.. 4 ] 일떄 굳이 (+버튼)을 10 - 현재숫자 만큼 누르는 것보다 (-버튼)을 누르는게 최소값.
• 눌러야 할 버튼이 [ 6.. 10 ] 일때 굳이 (-버튼) 누르는 것보단, (+버튼) 을 누르는 것이 최소값.
• 눌러야 할 버튼이 5 일때는 (+ 버튼) , (- 버튼) 둘다 확인 해야 한다.
  • 주어진 숫자가 5554 일 경우
    
    • (-버튼 ) 4번 누른다. --> 5550
    • (+버튼) 5번 누른다. --> 5600
    • (+버튼)4번 누른다. --> 6000
    • (-버튼)4번 누른다. --> 0 층 도달!
• 스택에 쌓이는 재귀 호출 개수가 최대 2 ^ 10 = 1024 임으로, 최적화 할 필요 없이, 브루트 포스를 사용하여 풀이했다. 

 

참고

처음에 배열 초기화를 뒤에 실수로 덜 해줘서..  index out of range 인데 런타임 에러가 떴다 .

에러 이름을 명시 안하고 단순히 런 타임 에러만 떠서 Time Limit Exception 에러로 착각하여, 브루트 포스가 아닌가? 하고 최적화를 하려고 하다가 몇 시간이 걸린 후 문제점을 파악했다. 

 에러가 뜨면 배열 index access 에 문제가 있나 없나 코드를 다시 한 번 체크해야 겠따.

프로그래머스에선 index out of range 에러도 에러 이름을 명시 안해주고 런타임 에러로 뜨니깐 주의할것. ! 

  /*cnt[9]를 까먹었다*/
  int cnt[] = {0,1,2,3,4,5,4,3,2};
  /*이게 맞는데....*/
    int cnt[] = {0,1,2,3,4,5,4,3,2,1};

코드

자바

import java.util.*;

class Solution {
    int cnt[] = {0,1,2,3,4,5,4,3,2,1};
    int answer= Integer.MAX_VALUE;
    
    public int solution(int cur) {
        
        helper(cur, 0);
        return answer;
    }
    public void helper(int cur, int val){
        if(cur < 10){
            int p = cur > 5 ? 1 : 0;
            answer = Math.min(cnt[cur]+p+val , answer);
            return;
        }
        if(cur % 10 <= 5){
            helper(cur / 10, cnt[cur%10] + val);
        }
        if(cur % 10 >= 5){
            helper(cur / 10 + 1, cnt[cur%10]+val);
        }
    }
}