프로그래머스 Lv2 문제입니다. 실전에 대비하기 위해 60분 시간제한을 두고 풀었습니다.

문제

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

[나의 풀이1]

⌛ 5분

from collections import deque

def solution(x, y, n):
    answer = 0
    cnt = 0
    
    queue = deque([(x,cnt)])
    
    while queue:
            
        now,cnt = queue.popleft()
        
        # print("------------------")
        # print("now : ",now," cnt : ",cnt)
        
        if now==y:
            answer = cnt
            return answer

        if now+n<=y:
            queue.append((now+n,cnt+1))
        if now*2<=y:
            queue.append((now*2,cnt+1))
        if now*3<=y:
            queue.append((now*3,cnt+1))
    
    return -1

초기 자연수 x, 목표 자연수 y가 주어지고 사용할 수 있는 3가지 연산(+n, x2, x3)이 있을 때, x에서 y로 변환하기 위해 최소 연산 횟수를 구하는 문제입니다.🐥🐥🐥

바로 Queue구조, BFS 알고리즘을 활용하여 구현하였으나 일부 케이스에서 시간초과가 발생하였습니다.

[나의 풀이2]

⌛ 45분

from collections import deque

def solution(x, y, n):
    answer = 0
    cnt = 0
    
    queue = deque([(y,cnt)])
    
    while queue:
            
        now,cnt = queue.popleft()
        
        # print("------------------")
        # print("now : ",now," cnt : ",cnt)
        
        if now==x:
            answer = cnt
            return answer

        if now-n>=x:
            queue.append((now-n,cnt+1))
        if now/2>=x and now%2==0 :
            queue.append((now/2,cnt+1))
        if now/3>=x and now%3==0 :
            queue.append((now/3,cnt+1))
    
    return -1

시간초과가 발생한 일부 케이스를 통과시키 위해 Queue에 추가되는 경우의 수를 줄이고자 하였습니다.🦔🦔🦔

이때 x에서 y로 변환하는 것이 아닌 y에서 x로 변환하는 관점으로 바꾸고, 사용 가능한 연산 중 x2, x3 곱셈을 /2, /3로 변환하였습니다.

포인트는 나눗셈 연산 시 나머지가 발생하는 케이스는 최종적으로 x로 변환할 수 없다는 뜻이므로 Queue에 추가하지 않는 것이였습니다.

[다른 사람의 풀이]

def solution(x, y, n):
    answer = 0
    s = set()
    s.add(x)

    while s:
        if y in s:
            return answer

        nxt = set()
        for i in s:
            if i+n <= y:
                nxt.add(i+n)
            if i*2 <= y:
                nxt.add(i*2)
            if i*3 <= y:
                nxt.add(i*3)
        s = nxt
        answer+=1

    return -1

Set() 구조를 활용하여 구현한 풀이입니다.🕊️🕊️🕊️

'나의 풀이'와 같이 사용 가능한 연산을 진행했을 때의 값이 y값 이하라면, Set()구조에 추가한 뒤

이후 Set() 객체안에 있는 요소가 y값으로 딱 맞아떨어질 때의 횟수를 반환하는 방식입니다.

감사합니다.