[프로그래머스] 숫자 변환하기 (python)

 

첫 번째 풀이

def solution(x, y, n):
    answer = 0
    sum_ls = [x]
    
    while sum_ls:
        if y in sum_ls:
            return answer
        
        sum = []
        for ls in sum_ls:
            if ls + n <= y:
                sum.append(ls + n)
            
            if ls * 2 <= y:
                sum.append(ls * 2)
            
            if ls * 3 <= y:
                sum.append(ls * 3)
            
        sum_ls = sum
        answer += 1
    return -1

 

 

 

BFS를 이용한 문제로 문제에서 사용할 수 있는 모든 연산을 사용해서 계산 후 y를 넘는 것은 계산 대상에서 제외하고 반복해서 계산하는 방식으로 코드를 작성하였다

 

대부분의 테케가 잘 풀렸지만 몇몇이 시간초과가 나서 어느 부분에서 그런지 생각해 봤지만 잘 떠오르지는 않았다

 

두 번째 풀이

def solution(x, y, n):
    answer = 0
    sum_ls = [x]
    
    while sum_ls:
        if y in sum_ls:
            return answer
        
        sum = []
        for ls in sum_ls:
            if ls + n <= y:
                sum.append(ls + n)
            
            if ls * 2 <= y:
                sum.append(ls * 2)
            
            if ls * 3 <= y:
                sum.append(ls * 3)
            
        sum_ls = list(set(sum)) ## 계산 값이 중복인 것을 제거
        answer += 1
    return -1

 

 

프로그래머스

위 글을 참고해서 문제를 풀이할 수 있었는데 

 

계산 결괏값이 중복인 것 때문에 반복 계산해서 시간이 오래 걸린다는 것을 알고 sum_ls의 중복을 제거하니까 테스트를 통과할 수 있었다