첫번째 코드
BFS를 이용해야겠다! 라고 생각을 했다.
처음에는 값만을 넣었는데, count가 정답을 구하기 위해 별도로 필요하므로 [값, count] 형태로 현재까지의 계산값과 계산 횟수를 표시한다.
계산할 수 있는 모든 값을 계산하고, y와 같은 경우 answer 리스트에 넣는다.
계산 횟수를 기준으로 정렬 한 후 계산 횟수가 가장 적은 경우만 불러온다.
from collections import deque
def solution(x, y, n):
answer = []
count = 0
queue = deque()
queue.append([x, count])
while queue:
now = queue.popleft()
count = now[1] + 1
if now[0] == y:
answer.append(now)
else:
if now[0] < y:
queue.append([now[0]*3, count])
queue.append([now[0]*2, count])
queue.append([now[0]+n, count])
answer.sort(key = lambda x: x[1])
if not answer:
return -1
else:
return answer[0][1]
테스트 케이스는 통과하지만, 불필요한 연산이 많아 시간초과가 발생한다.
두번째 코드
정답에 해당하는 리스트를 만들어서 sort 하는 방법은 추가로 계산이 들어가므로, 해당 부분을 제거한다.
from collections import deque
def solution(x, y, n):
answer = []
count = 0
queue = deque()
queue.append([x, count])
while queue:
now = queue.popleft()
count = now[1] + 1
if now[0] == y:
answer = now
break
else:
if now[0] < y:
queue.append([now[0]*3, count])
queue.append([now[0]*2, count])
queue.append([now[0]+n, count])
if not answer:
return -1
else:
return answer[1]
테스트 케이스는 통과하지만, 부분부분 시간초과가 발생한다!
세번째 코드
x에서 y로 가는 계산을 하는 경우 무한으로 커질 수 있으므로, 반대로 y에서 x를 구하는 방법을 통해 계산량을 줄인다!
from collections import deque
def solution(x, y, n):
answer = []
count = 0
queue = deque()
queue.append([y, count])
while queue:
now = queue.popleft()
count = now[1] + 1
if now[0] == x:
answer = now
break
else:
if now[0] > x:
if now[0] % 3 == 0:
queue.append([now[0]//3, count])
if now[0] % 2 == 0:
queue.append([now[0]//2, count])
queue.append([now[0]-n, count])
if not answer:
return -1
else:
return answer[1]
통과!
링크
programmers/프로그래머스/2/154538. 숫자 변환하기 at main · ornni/programmers
repository for recording Programmers Algorithm problem solving - ornni/programmers
github.com