프로그래머스 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값으로 딱 맞아떨어질 때의 횟수를 반환하는 방식입니다.
감사합니다.