23.02.17 파이썬 코딩 퀴즈#161 숫자 변환하기 (프로그래머스 스쿨)

이번 문제는 숫자 변환하기 문제이다.

주어진 조건에 따라 x+n, x*2, x*3 을 실행하게 되며, 목표 숫자인 y로 변환할 때의 최소 연산 횟수를 구해야 한다. 만약 x를 변환하여 y를 만들 수 없는 경우라면 -1을 return 해야 한다.

사용할 수 있는 연산은 3개 이지만, 순서도 없고 하나만 사용해도 무관하다.

 

접근하는 방법은 두가지이다, x에 주어진 연산을 적용에 y 를 만들던가, 아니면 y에 주어진 연산으로 역으로 계산해서 x 를 만들던가.

내가 생각한 풀이법은 y에 연산을 적용하는 방법이다. 이 방법을 택한 이유는 어짜피 target 이 가능한 방법을 찾는 것이고, x를 기준으로 하게 되면 불필요한 연산이 더 많아지게 되기 때문이다.

예를 들어 x 가 15이고 y 가 50, n이 10 인 경우를 예를 들어 보자.

첫번째 3가지 연산을 적용하면 x = [30,45,25] 가 된다.

그리고 각 요소들을 기준으로 다시 연산을 하게 되면 [[60,90,40],[90,135,55,],[50,75,35]] 가 된다.

눈으로는 바로 찾을 수 있지만 이를 또 코드로 찾게되면 40을 먼저 탐색한 다음 50을 찾고 50을 연산한 횟수를 반환하게 된다.

반대로 y를 기준으로 연산을 하게 되면

첫번째 연산에서 [25,40] 두가지만 나온다. 50은 3의 배수가 아니기 때문에 2로 나눈 값과, 10을 뺀 값 두가지만 확인하면 된다.

또한 25 역시 2또는 3의 배수가 아니므로 [ [15], [20, 30] ] 이렇게 두 요소에 대해 총 3가지의 경우가 도출된다.

세번째 연산에서는 [[5,5],[10,10],[15,10,20]] 이다.이 또한 조건에 의해 [[10,10],[15,10,20]] 만 남게 된다.

pop()을 이용한 코드이기 때문에 좀더 빠른 속도의 작업을 원한다면 deque 라이브러리 사용을 추천한다.