[프로그래머스/Python] 숫자 변환하기

문제 정보

제목 : 숫자 변환하기

난이도 : Lv.2

사용 언어 : Python

문제 링크

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

 

문제 설명

자연수 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

입출력 예

x	y	n	result
10	40	5	2
10	40	30	1
2	5	4	-1

입출력 예 설명

입출력 예 #1
x에 2를 2번 곱하면 40이 되고 이때가 최소 횟수입니다.

입출력 예 #2
x에 n인 30을 1번 더하면 40이 되고 이때가 최소 횟수입니다.

입출력 예 #3
x를 y로 변환할 수 없기 때문에 -1을 return합니다.

---

나의 풀이

첫번째 시도

BFS를 통해 문제를 해결하려 했습니다. q에 처음 값 (x,0)을 저장후 while문을 통해 q의 값을 a와 count에 저장합니다.

a가 y보다 크면 continue하고, y와 같으면 answer에 count의 값을 저장한 후 리턴합니다. 아니라면 a를 각각의 방식으로 연산한 값을 q에 저장합니다. 이것은 q가 비워질때까지 반복합니다.

이렇게 문제를 푸니 시간초과라는 문제에 마주하게 되었습니다.

from collections import deque

def solution(x, y, n):
    answer = -1
    q = deque()
    
    q.append((x,0))
    
    while( q ) :
        a,count = q.popleft()
        
        if a > y:
            continue
        elif( a == y) :
            answer = count
            break
        else :
                q.append( (a + n,count+1) )
                q.append( (a * 2,count+1) )
                q.append( (a * 3,count+1) )
    return answer

다른 시도

시간이 오래 걸리는 것을 줄여야했습니다. 여러 방법을 찾아보던 중 y+1의 길이만큼 리스트를 생성해두고, 리스트의 인덱스를 x를 변환하는 값으로 하여 쉽게 값을 구할 수 있도록 했습니다. for문을 이용해 ca값을 구하고 ca가 y보다 크거나 c[ca]의 값이 있으면 continue합니다. 그리고 ca와 y가 같다면 c[a]+1을 하여 리턴합니다. q에 ca값을 저장해주고 c[ca]에는 c[a]+1한 값을 저장합니다. 모든 반복이 끝나도 결과를 얻지 못하면 변환값을 찾지 못한 것이므로 -1을 리턴합니다.

 

코드

from collections import deque

def solution(x, y, n):
    q = deque()
    c = [0 for i in range(y+1)]
    
    if ( x == y ) :
        return 0
    q.append(x)
    while( q ) :
        a = q.popleft()
        for i in range(3) :
            if ( i == 0 ) :
                ca = a + n
            if ( i == 1 ) :
                ca = a * 2
            if ( i == 2 ) :
                ca = a * 3
                
            if ca > y or c[ca] :
                continue
            
            if ca == y :
                return c[a]+1
            
            q.append(ca)
            c[ca] = c[a] + 1
            
    return -1