[프로그래머스] Lv2. 마법의 엘리베이터

🔍 문제

📝 풀이

BFS 풀이

10의 단위로 끊어서 방문하기 때문에 최대 9자리여도 가능한 가지수는 2^9 = 512 정도라 BFS로 풀었다.

limit는 이 값을 넘어가는 값을 가지면 더 이상 최소가 될 가능성이 없다고 판단하고 설정해둔 한계 값. 3자릿수라면 1000, 4자릿수라면 10000과 같은 식으로 정해뒀다.

def solution(storey):
    
    Q = deque([(storey, 1, 0)])
    answer = 1e9
    limit = 10 ** len(str(storey))
    while Q:
        story, c, push = Q.popleft()
        
        if story == 0:
            answer = min(answer, push)
            continue
        
        x = story % (10**c)
        step = int(str(x)[0])
        
        if 0<=story-x:
            Q.append((story-x, c+1, push+step))
        if story+(10**c-x)<=limit:
            Q.append((story+10**c-x, c+1, push+10-step))
    
    return answer

from collections import deque

그리디

1의 자리부터 차례대로 1~4인 경우 아래로, 6~9인 경우 무조건 위로 올라가는 방식을 택하는 그리디.

4이하인 경우는 아래로 내려가는게 무조건 위로 올라가는 것보다 적을 수 밖에 없다. 만약 위로 올라가서 숫자를 올림 한다고 해도 마찬가지. 94를 예시로 들었을 때 위로 올라간다고 치면 100이 되는데, 6 -> 1 = 7이지만 내려간다고 치면 4 -> (90) -> 1 -> (100) -> 1 -> (0) = 6으로 더 낮다.

5의 경우 애매한데, 위로 올라가나 내려가나 똑같기 때문이다. 이때는 더 위의 자리수를 보고 1~4인 경우는 아래로 내려가는 게 유리하기 때문에 내려가는 쪽을 택할 수 있게 하고, 6~9인 경우는 위로 올라가는 게 유리하기 때문에 위로 올라가는 쪽을 택하면 된다.

만약 1의 자리가 5이고 10의 자리가 5라면 위든 아래든 똑같은 결과가 나오기 때문에 위/아래 둘 중 하나를 택해서 가면 된다.

사실 이 방식은 되는 방법이 아닐 것 같아서 시도도 안 해봤는데 다들 이 방식으로 풀었고 위의 BFS보다 훨씬 짧게 걸린다.

def solution(storey):
    answer = 0
    
    while storey:
        step = storey % 10
        
        if step < 5:
            storey -= step
        elif step > 5:
            storey += 10-step
        else:
            story = storey // 10 % 10
            if story >= 5:
                storey += step
            else:
                storey -= step
  
        storey //= 10
        answer += 10-step if step >= 5 else step
        
    return answer