[PS] 프로그래머스 level 2 마법의 엘레베이터 java 풀이

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

프로그래머스

초기 문제 접근

1. 처음엔 백트래킹? BFS? 등 완전 탐색을 생각했다.
2. 근데 그건 말이 안 된다. 너무나 많은 경우의 수가 존재한다.
3. 그리디인가? 동전 거스름돈처럼 큰 수부터 나누면 되는가?
4. 근데 음수도 존재해서 이것도 아니다.
5. 직접 if 문으로 조건을 따져야 하는 건가?  현재 자릿수가 6이면 10에서 빼는 거로 하고..
6. 그러면 올림의 경우, 앞자리에 1을 더해야 하는데.. 만약 더하는 게 더 많은 돌을 필요로 하면..? (머릿속이 복잡해지기 시작)

문제 풀이

1. 뒷자리에서 올림을 수행했는지 carry라는 변수에 1 또는 0 저장
2. 맨 뒷자리부터 시작한다. (1234이면 4부터) 
3. 현재 자릿 수의 수가 5보다 크거나, 5인데 앞 자릿수가 5보다 같거나 크면 올림을 수행한다.
   예를 들어 65를 생각해 보자. 일의 자리가 5일 경우, 십의 자리 수가 6이므로 올림을 수행하면
   70 (65 + (+1 x 5 )) 이 된다. 여기서 사용한 동전은 5(10 - 현재 자릿 수의 숫자)이며, 이후 앞자리에 1을 더해야 하므로 carry = 1을 선언한다.
4. 만약 내림을 사용해야 하면, 현재 자릿 수의 숫자만큼만 사용하면 되며, carry = 0으로 선언한다.
5. 다음 자릿수를 수행하기 위해 storey /= 10을 수행한다.
6. 마지막으로 올림을 수행했다면(carry == 1), answer + 1을 리턴한다. 왜냐하면, 최종 숫자가 65에서 올림을 수행해서 70이 되고, 7을 검사할 때 현재 자릿 수가 5보다 크므로 10 - 7인 3이 더해진다. 하지만 이는 70을 100으로 만든 것이며, 다시 -100을 수행해야 하기 때문에 마지막에 + 1을 해야 한다.

코드

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

예시

65를 생각해 보자

current == 5가 true이고, 십의 자리 수 6이 >= 5 이므로 

answer = 5 (10 - 5)가 되고 carry = 1이다.

storey /= 10을 수행하여 storey = 6이다.

 

그다음 십의 자릿수 6을 검사한다. 이전 단계에서 올림을 수행했으므로

current = 6 % 10 + 1  = 7이다.

current > 5가 true 이므로 

answer = 기존 5 + 3(10 - 7) = 8이다.

 

최종적으로 carry = 1인데, 이는 current인 7을 10으로 만들었다는 것을 의미하기 때문에, 다시 -10을 해주어야 해서

answer + 1을 한다.

따라서 9이다.

왜 (storey / 10 ) % 10 > 5가 아니라 >= 이어야 하는가?

올림을 하는 것이 더 효율적일 수 있기 때문이다.

 

• 다음 자릿수에 대한 최적화 기회 제공:
  • 현재 자릿수에서 올림을 하게 되면 다음 자리수에 1이 더해진다.
  • 이렇게 올림으로 인해 발생한 carry는 다음 자릿수의 값에 영향을 주며, 이를 통해 다음 자리수를 0에 더 가깝게 만들 수 있는 기회를 제공한다. 예를 들어, 다음 자리수가 5 이상이라면 올림으로 인해 다음 자리수가 더 높은 자리에서 0으로 조정될 가능성이 생긴다.
• 큰 자리수의 영향 감소:
  • 현재 자릿수에서 올림을 선택하면 높은 자리수에서 전체 숫자를 줄일 수 있는 기회를 만든다.
  • 높은 자릿수의 숫자는 숫자 자체가 크기 때문에, 이러한 자릿수를 줄이는 것은 전체적으로 더 큰 차이를 만들 수 있다.