[Greedy] 마법의 엘리베이터 - Python / JavaScript

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

프로그래머스

 

[문제 간단 요약]

• 엘리베이터가 현재 층 storey에 있음.
• 버튼을 눌러 1의 자리 단위로 올리거나 내리는 방식으로 0층까지 이동해야 함.
• 한 번 누를 때마다 1의 자리 기준으로 +1 또는 -1만 가능.
• 버튼 누르는 횟수를 최소화해야 함.
• 반환: 최소 버튼 누름 횟수.

[문제 해결 방안]

• 핵심 아이디어: 그리디(Greedy) + 자리수 처리
  1. 현재 층의 1의 자리(stor = storey % 10)를 확인
     • stor < 5: 그냥 내려가는 것이 최소
     • stor > 5: 올라가서 반올림 처리 후 다음 자리 올림
     • stor == 5: 그 다음 자리(십의 자리)를 확인해서 올라가는 게 유리한지, 내려가는 게 유리한지 판단
  2. 각 자리마다 최소 버튼 수를 누적
  3. 모든 자리(몫이 0 될 때까지) 반복
• 이 방식은 각 자리수에서의 최적 선택이 전체 최적해로 이어지는 그리디 구조임.

[문제 해결 코드 - python]

def solution(storey):
    result = 0
    while storey:
        stor = storey % 10
        if stor > 5:
            result += 10 - stor
            storey += 10
        elif stor < 5:
            result += stor
        else:  # stor == 5
            if (storey // 10) % 10 > 4:  # 십의 자리 확인
                storey += 10
            result += stor        
        storey //= 10
    return result

 

[문제 해결 코드 - javascript]

function solution(storey) {
    let answer = 0;
    
    while (storey) {
        let stor = storey % 10
        if (stor > 5) {
            storey += 10
            answer += (10-stor)
        } else if (stor < 5) {
            answer += stor
        } else {
            if (Math.floor(storey / 10) % 10 > 4) {
                storey += 10
            }
            answer += stor
        }
        storey = Math.floor(storey / 10)
    }
    return answer;
}