<프로그래머스> 마법의 엘리베이터(Lv.2)

[깃허브]

https://github.com/heesoo-park/ForCodeKata/tree/main/%EB%A7%88%EB%B2%95%EC%9D%98%20%EC%97%98%EB%A6%AC%EB%B2%A0%EC%9D%B4%ED%84%B0

[프로그래머스]

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

 

이 문제는 그냥 자력으로는 못 풀었다.

내가 생각하고 진행했던 방식으로는 끝까지 해도 풀어내지 못했을 것이다.

 

처음에 이 문제를 딱 보고 생각났던 문제는 1로 만들기나 피로도같은 문제들이었다.

해당 문제들은 재귀나 DP(메모이제이션)의 유형이었다.

그래서 그렇게 접근하려는데 숫자 최대 제한이 100000000...?! 

1억을 배열의 크기로 그냥 설정해버리니까 에러가 뜨더라

그래도 떠오르는 방법이 없었기에 진행했다.

하고보니까 재귀와 DP 모두 느리거나 인덱스 접근에 관련해서 에러가 계속 발생했다.

이걸로 알 수 있는 공통적인 문제는 숫자 하나씩 하나씩 접근을 해야하기 때문에 최대 1억개의 배열이 필요하다는 거였다.

이건 내가 생각하기에 코드에서 해결할 수 있는 부분이 아니었다...

 

그렇게 이 문제는 내 손을 떠났다...

도움이 필요했다.

그리고 거기서 본 것은 그리디 알고리즘이었다.

'여기서 이게 왜 나와?' 라는 느낌이었지만 생각해보지 않았던 알고리즘은 아니었다.

하지만 항상 최소한의 버튼을 눌러야하는데 '이걸 현재에서 최선의 선택을 하는 것으로 그 값이 나올까?' 라는 생각이 들어서 패스했던 거였다.

다른 사람의 풀이를 보고나니 되는구나 싶었다.

왜냐하면 제일 작은 자릿수부터 작은 수로 클릭를 해서 최종적으로 큰 자릿수에서 큰 숫자로 0까지 이동하는게 최소한의 버튼 클릭을 가져가게 될 것이기 때문이다.

여기까지 이해하는데도 시간이 걸렸다.

그리디 알고리즘은 정말 초반에 이게 되는 이유를 혼자서 정리하는 것만 잘되면 이후 접근은 좀 쉬워지는 것 같다.

 

물론 나는 아직 아니다.

이후 접근도 지금 내 수준에서는 떠올리기 버거웠을 거 같다.

그리디 알고리즘을 가지고 가는 다음 스텝은 5를 기준으로 잡는 것이었다.

현재 자릿수의 숫자가 5보다 작으면 마이너스를 하고, 5보다 크면 플러스를 하는 거다.

같을 때는 다음 자릿수의 숫자를 보고 판별하면 된다.

다음 자릿수의 숫자가 5보다 크거나 같으면 플러스를 하고, 5보다 작으면 마이너스를 하는 거다.

그럼 이걸 할 때 그냥 숫자를 그대로 두고 하느냐...?

그렇지 않고 해당 자릿수 판별이 끝나면 나누기 10을 해서 다음 자릿수이지만 1의 자릿수에서 판별할 수 있도록 했다.

나는 모든 케이스에 플러스 마이너스를 해야한다고 생각했었는데 나누기 10을 하니까 다음 자릿수에 영향을 주는 것만 연산하면 되겠더라

 

해당 방법으로 작성한 코드는 다음과 같다.

class Solution {
    fun solution(storey: Int): Int {
        var answer: Int = 0
        var cur = storey

        while (cur != 0) {
            // 현재 자릿수
            if (cur % 10 == 5) {
                // 다음 자릿수
                if (cur / 10 % 10 >= 5) {
                    answer += 5
                    cur += 10
                } else {
                    answer += 5
                }
            } else if (cur % 10 < 5) {
                answer += cur % 10
            } else if (cur % 10 > 5) {
                answer += (10 - cur % 10)
                cur += 10
            }

            cur /= 10
        }

        return answer
    }
}

 

그리디, DFS, BFS, 재귀, DP... 이것만 뚫려도 속이 상쾌해질텐데...