[ 프로그래머스 / LV2 / 파이썬 Pyhton ) 마법의 엘리베이터

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

프로그래머스

 

코드

---

def solution(s):
    answer =  0
    stack = list(map(int,list(str(s))))[::-1]
    while stack:
        x = stack.pop()
        if x > 5: # 5보다 작다면
            if stack:
                stack[-1] += 1
                answer += 10-x
            else:
                answer += 10-x+1
        elif x < 5: # 5보다 크다면
            answer += x
        else: # 5와 같다면
            if stack and stack[-1] >= 5: # 다음 숫자가 5보다 크거나 같다면
                stack[-1] += 1
                answer += 10-x
            else:
                answer += x
    return answer

 

풀이

---

문제를 읽고 든 생각은 요즘 젊은 사람들은 모를 수도 있으나 어릴 적에 많이 했던 놀이인  "스무고개" 또는 "업다운" 과 비슷하다는 느낌을 받았다.

두 놀이의 공통점은 정해져 있는 정답을 향해 기준을 세워 정확한 값은 아니더라도 근사치로 계속해서 접근한다는 것이다.

예를 들어, 6가 정답이라면 10보다 작다 -> 5보다 크다 -> 8보다 작다 -> 6보다 크지 않다 -> 6 이런 식으로 말이다.

그래서 십의 제곱수만큼씩 더하고 뺄 수 있으므로 storey의 초기값보다 큰 십의 제곱수를 찾아 위와 같은 방법으로 시도해봤으나 시간초과가 나고 말았다.

 

질문하기 탭에서 결국 힌트를 얻었고 그 힌트를 활용해 위와같은 나만의 풀이를 만들었다.

 

결과적으로 생각해본다면 -1,+1,-10,+10 과 같은 10의 거듭제곱 수들을 이용해서 storey를 모두 채워야 끝나는 일이다.

10의 거듭제곱 수들을 이용한다는 말을 잘 생각해보면 자리수별로 처리할 수 있다는 걸 깨달을 수 있다.

 

예를 들어, 예시에 나온 2554와 같은 경우 1*4 + 10*5 + 100*5 + 1000*2 = 2554이므로 16이 답이다. 물론 이렇게 간단하다면 LV1정도 수준도 되지 않았을 것이다. 이렇게 간단하게 끝나는 경우는 모든 자릿수를 내리는 경우이다.

문제의 첫 번째 예시인 16의 경우에는 1*6 + 10*1 = 16이므로 7이 될 것 같지만 정답은 6이다. 왜냐하면 16을 10+6이 아닌 20-4로 계산하기 때문이다. 

이런 방식으로 이 문제에서 답을 구하는 방법에는 자리수를 올리는 경우, 자리수를 내리는 경우 두 가지가 있다.

 

그렇다면 지금까지 우리가 알게된 내용은 자리수 별로 탐색하면서 그 숫자의 자리수를 올릴지, 말지를 결정해야 한다는 것이다. 이제 자리수를 올리는 기준에 대해 생각해봐야 한다.

간단하게 생각해보면 자리수를 올려야 하는 숫자는 윗 자리수와 가까운 수, 내려야 하는 숫자는 아래 자리수와 가까운 수이다.

x라는 숫자가 있다고 하면 10-x가 x보다 작다면 올리고 반대면 내리는 것이다.

• 올려야 하는 수 : 6,7,8,9
• 내려야 하는 수 : 0,1,2,3,4

여기서 빠진 수가 있다. 바로 5이다. 5는 10-5=5로서 올리는 기준과 내리는 기준이 같기 때문이다. 그렇다고 똑같기 때문에 아무 기준이나 적용시킬 수는 없다.

 

다음과 같은 예시를 보자.

555 = 5*100 + 5*10 + 5*1 => 15 (555 -> 550 -> 500 -> 0)

        = 1*1000 - 4*100 - 4*10 + 5*1 => 14  (555 -> 560 -> 600 -> 1000 -> 0)

위와 같이 첫 번째 자리의 5를 올림으로써 더 적은 개수로 숫자를 만들어 낼 수 있다.

 

이 때, 5를 올릴지 말지의 기준은 바로 다음 자리의 숫자이다. 자리수를 올린다는 말은 다음 자리의 수에 1을 더한다는 말과 같다.

즉, "다음 자리의 수에 1을 더했을 때, 그 수가 올려야 하는 수와 내려야 하는 수 중 어느 곳에 포함되는가" 를 따져봐야 한다.

 

다시 555 예시를 보게 되면 첫 번째 자리 5에서 자리수를 올리면 560이 된다. 두 번째 자리가 5에서 6이 되었으므로 올려야 하는 수가 된다. 그리고 기존의 5를 만들려면 1*5를 하거나 10-5를 해서 5개의 수가 필요했다면 6으로 바뀌어서 4개의 수가 필요해진 셈이다.

 

따라서 다음 자리의 수에 따라 5를 올릴지 말지 결정을 해야 한다. 다음 자리의 수가 5 이상이라면 올림, 4이하라면 내림을 해야한다.

 

굳이 스택을 사용하지 않아도 되지만 스택으로 하는게 간편해보여서 사용해봤다. 근데 문제를 해결하고 다른 사람의 풀이를 보니 4줄..? 정도로 해결한 사람이 있던데..정말 대단한 것 같다.