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

1일 1PS 81일차!

📚 문제

---

[Level 2] - 마법의 엘리베이터

💡 풀이 과정

---

• BFS 와 메모지에이션을 통해 풀어낼 수 있다.
• 가장 작은 횟수로 0 을 만들어야하기에 각 숫자에 cnt 를 가장 적게 도착하는 것을 선별하면 된다.
• 1948 이라는 숫자를 0으로 만들기 위해서는
  • 1948 -> 1950 -> 2000 -> 0 으로 만들어내는 것이 가장 최적의 루트이다.
  • 결국 가장 끝 자리수부터 처리해아한다는 뜻이다.
  • storey % 10 을 통해 가장 마지막 자리수를 표시하고 storey //= 10 을 통해 가장 마지막 자리수를 제거할 수 있다.
• 이를 통해 1948 에서 dp[1940] = 8, dp[1950] = 2
  • dp[1900] = min(dp[1940] + 4, dp[1950] + 5)
• 이처럼 진행할 수도 있지만 잘 살펴보면 위의 결과들은 이미 정해져 있다.

• 결국 작은 자리수부터 지워나가야하는 것은 명확하다.
  • 9 의 경우
    • 9 + 1 - 10 (2번)
    • 9 - 9 (9번)
  • 6 의 경우는
    • 6 + 4 - 10 (5번)
    • 6 - 6 (6번)
  • 5 의 경우는
    • 5 + 5 - 10 ( 6번 )
    • 5 - 5 (5번)
  • 위를 통해 6 ~ 9 는 무조건 더하는 것이 이득이며, 0 ~ 5 는 무조건 빼는 것이 이득이라 볼 수 있다.
  • 65 의 경우는
    • 65 + 5 - 70 (5 + 7 번) or 65 + 5 + 30 - 100 ( 5 + 3 + 1 번)
    • 65 - 5 - 60 ( 5 + 6 번) or 65 - 6 + 40 - 100 ( 5 + 4 + 1 번)

  • 위 예시를 통해 5는 예외가 존재함에 주의해야한다.

  • 다시 생각해보면 5 자체는 +- 는 동일하게 5번이며 그 다음 자리 수가 + 1 or - 1 이 되는 것을 볼 수 있다. 따라서 다음 자리가 0 ~ 4 인 경우에는 빼는 것이 유리하며 6 ~ 9 인 경우는 더하는 것이 유리하다.

  • 55 의 경우는
    • 55 + 5 + 40 - 100 = (5 + 4 + 1 번)
    • 55 - 5 - 50 = (5 + 5)
    • 으로 동일하다. 따라서 다음 자리가 5인 경우는 더하거나 빼거나 모두 상관없다!

📌포인트

---

• 시간복잡도
  • 확실한 구분과 처리가 가능한 경우 BFS 보다는 빠른 코드를 사용하자.

💻 코드

---

def solution(storey):
    answer = 0
    
    while storey:
        temp = storey % 10
        # 6 ~ 9 경우 더해주어야한다.
        if temp > 5:
            answer += (10 - temp)
            storey += 10
        # 0 ~ 4 경우 빼줘야한다.
        elif temp < 5:
            answer += temp
            storey -= temp
        # 5 인 경우 다음 자리수를 미리 확인하고 0 ~ 5 인 경우에 뺴고 6 ~ 9 는 더하는 것으로 처리한다. 
        # 더하고 빼는 횟수가 모두 5 이므로 동일하게 처리한다. 
        else:
            if (storey // 10) % 10 > 5:
                storey += 10
            answer += temp
            
        # 가장 뒷 자리수를 처리한다.
        # 이때 가장 뒷자리수가 처리되기에 앞서서 계산에 신경쓰지 않아도 된다.
        storey //= 10

    return answer