프로그래머스 - 숫자 변환하기

입력에 대해 목표값까지 더하거나 나누는 문제

 

이런 문제는 당장 생각나는 큐를 사용하는 완탐 기반 방법이 두개가 있다.

 

1. 입력을 목표에 맞춰서 더하거나 곱하는 방법

2. 목표를 입력에 맞춰서 빼거나 나누는 방법

 

이런 문제는 2번이 적합하다.

1을 +1, *2, *3만을 사용하여 10에 하려면 최단 방법은 여러가지가 있겠지만 우선 *3 *3 +1이 생각난다.

 

1번으로 접근하면

1에 대해서 3번 연산, 2에 대해서 3번연산, 3에 대해서 3번연산, ... 이렇게 가지만

 

2번으로 접근하면

10에 대해서 2번 연산(-1, /2), 9에 대해서 2번 연산(-1,/3),  5에 대해서 1번 연산, 8에 대해서 2번 연산, 3에 대해서 2번 연산, 

 

이렇게 진행된다.

 

즉 연산 횟수 자체가 많이 줄어든다.

 

from collections import deque

def solution(x, y, n):
    answer = -1
    q = deque([[y, 0]])
    while q:
        y, cnt = q.popleft()
        if y <= 0:
            continue
        else:
            if y == x:
                return cnt
            q.append([y - n, cnt + 1])
            if y % 2 == 0:
                q.append([y // 2, cnt + 1])
            if y % 3 == 0:
                q.append([y // 3, cnt + 1])
    return answer

여기서 최적화를 진행하자면, 큐에서 꺼낸 후 검사하는 것보다 큐에 넣기 전에 검사하는게 더 빠를 수 있다.

 

이렇게 최적화를 하면 중요한 것은 y와 x가 같은 경우이다.

from collections import deque

def solution(x, y, n):
    answer = -1
    if y == x:
        return 0
    q = deque([[y, 0]])
    while q:
        y, cnt = q.popleft()
        if y <= 0:
            continue
        else:
            if y - n == x:
                return cnt + 1
            q.append([y - n, cnt + 1])
            if y % 2 == 0:
                if y // 2 == x:
                    return cnt + 1
                q.append([y // 2, cnt + 1])
            if y % 3 == 0:
                if y // 3 == x:
                    return cnt + 1
                q.append([y // 3, cnt + 1])
    return answer