[프로그래머스] LV.2 숫자 변환하기 / 파이썬(Python)

 

📜 문제 설명

자연수 x를 y로 변환하려고 합니다. 사용할 수 있는 연산은 다음과 같습니다.

• x에 n을 더합니다
• x에 2를 곱합니다.
• x에 3을 곱합니다.

자연수 x, y, n이 매개변수로 주어질 때, x를 y로 변환하기 위해 필요한 최소 연산 횟수를 return하도록 solution 함수를 완성해주세요. 이때 x를 y로 만들 수 없다면 -1을 return 해주세요.

 

제한사항

• 1 ≤ x ≤ y ≤ 1,000,000
• 1 ≤ n < y

 

🔗 문제 링크

https://school.programmers.co.kr/learn/courses/30/lessons/154538

프로그래머스

 

💡 문제 풀이

문제를 보자마자 간단하게 풀어보려고 접근해봤다.

정말 간단하게 풀 수 있도록 만들어진 문제라면 이런 경우에는 대개 x에서 y를 만드는 것보다 y를 x로 거꾸로 만드는게 쉽다. 그래서 정말 간단하게 접근해봤고 간단하게 틀려먹었다 😂

50퍼센트 밖에 안나온다. x를 빠르게 y로 만드는 문제인데 아래의 코드처럼 짜면 엣지 케이스에서 우수수 떨어질 수 밖에....

# 정답율 50퍼센트 틀린 코드
def solution(x, y, n):
    answer = 0
    
    while y != x:
        if y - n == x:
            y -= n
            answer += 1
        elif not y % 3:
            y //= 3
            answer += 1
        elif not y % 2:
            y //= 2
            answer += 1
        else:
            return -1
    
    return answer

 

그래서 bfs로 다시 접근한다. 간단해 보이는 풀이지만 꽤 오래 헤매서 나온 코드이다.

out of range를 n 번 이상 겪고 풀 수 있었던 코드

코드의 로직은 꽤 간단하다.  x와 y는 백만 이하의 숫자니까 백만일 크기의 리스트를 만든다.

1. x번째 인덱스가 시작점이니까 1번으로 지정한다.
2. x를 시작으로 가능한 연산 (x + n, x * 2, x * 3)이 범위 안에 있는 경우 해당 연산이 된 곳의 인덱스를 모두 2로 지정한다.
3. 2번의 과정을 반복한다.
4. y - 1 번째 인덱스에 들어있는 값이 정답이다.

# 성공 코드
from collections import deque
maxNum = 1000000

def bfs(x, y, n):
    check = [0] * (maxNum + 1)
    check[x] = 1
    
    queue = deque()
    queue.append(x)
    
    while queue:
        cur = queue.popleft()
        
        if not check[cur + n] and 0 <= cur + n <= maxNum:
            queue.append(cur + n)
            check[cur + n] = check[cur] + 1
        if not check[cur * 2] and 0 <= cur * 2 <= maxNum:
            queue.append(cur * 2)
            check[cur * 2] = check[cur] + 1
        if not check[cur * 3] and 0 <= cur * 3 <= maxNum:
            queue.append(cur * 3)
            check[cur * 3] = check[cur] + 1
    
    return check[y] - 1

def solution(x, y, n):
    answer = bfs(x, y, n)
    return answer