[프로그래머스] 숫자 변환하기 - Python

문제

---

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

프로그래머스

 

• 소요 시간 : 1시간
• 난이도 : LV 2

나의 풀이

---

1차 시도

접근 방법

재귀를 이용하여 모든 경우의 수를 탐색한다. 

y에서 x를 만들기 위해 n을 빼고, 3으로 나누고, 2로 나눈다. 

시간복잡도

매번 3가지 연산이 가능하므로, 최악의 경우에는 모든 경로를 탐색하게 될 수 있다. 
최악의 경우 시간 복잡도는 O(3^d)가 될 수 있다. 여기서 d는 y에서 x로 도달하기 위한 최대 깊이이다.

코드

def solution(x, y, n):
    answer = int(1e9)
    
    def dfs(num, cnt):
        nonlocal answer
        
        if num == x:
            answer = min(answer, cnt)
            return 
        
        if num < x:
            return 
        
        if ((num - n) % x == 0):
            dfs(num - n, cnt+1)
            
        if ((num / x) % 3 == 0):
            dfs(num / 3, cnt+1)

        if ((num / x) % 2 == 0):
            dfs(num / 2, cnt+1)
        
    dfs(y, 0)
    
    if answer == int(1e9):
        return -1 
    return answer

 

결과 : 실패

테스트 1 〉	통과 (0.01ms, 10.2MB)
테스트 2 〉	통과 (0.01ms, 10.4MB)
테스트 3 〉	통과 (0.01ms, 10.2MB)
테스트 4 〉	통과 (0.01ms, 10.1MB)
테스트 5 〉	실패 (런타임 에러)
테스트 6 〉	통과 (0.00ms, 10.2MB)
테스트 7 〉	실패 (0.02ms, 10.1MB)
테스트 8 〉	통과 (0.02ms, 10.1MB)
테스트 9 〉	실패 (런타임 에러)
테스트 10 〉	실패 (런타임 에러)
테스트 11 〉	실패 (0.01ms, 10.2MB)
테스트 12 〉	통과 (0.01ms, 10.1MB)
테스트 13 〉	통과 (0.01ms, 10.1MB)
테스트 14 〉	실패 (0.01ms, 10.1MB)
테스트 15 〉	통과 (0.05ms, 10.2MB)
테스트 16 〉	실패 (0.01ms, 10.1MB)

 

실패 요인

1.  (x = 1, y = 1,000,000, n=1)일 때 재귀 오류 런타임 에러가 발생한다. 

2. 조건이 잘못되었다. x로 나누지 말고 3, 2로만 나눴을 때 0이 되는지만 체크해도 된다. n도 마찬가지로 n을 뺏을 때 x이상인지만 보면 된다. 

---

2차 시도

접근 방법

1. 가지치기 : cnt 가 answer보다 클 경우 최소 연산 횟수를 이미 넘었기 때문에 return 한다.

2. 조건문을 수정하였다. 

코드

def solution(x, y, n):
    answer = int(1e9)
    
    def dfs(num, cnt):
        nonlocal answer
        if num == x:
            answer = min(answer, cnt)
            return 
        
        if num < x or cnt > answer:
            return 
        
        if (num % 3 == 0):
            dfs(num / 3, cnt+1)

        if (num % 2 == 0):
            dfs(num / 2, cnt+1)

        if (num - n >= x):
            dfs(num - n, cnt+1)
            
    dfs(y, 0)
    
    if answer == int(1e9):
        return -1 
    return answer

 

결과 : 시간초과

테스트 1 〉	통과 (0.01ms, 10.1MB)
테스트 2 〉	통과 (0.00ms, 10.1MB)
테스트 3 〉	통과 (0.00ms, 10.2MB)
테스트 4 〉	통과 (0.00ms, 10.2MB)
테스트 5 〉	통과 (60.47ms, 10.2MB)
테스트 6 〉	통과 (0.00ms, 10.1MB)
테스트 7 〉	통과 (34.44ms, 10.3MB)
테스트 8 〉	통과 (0.01ms, 10.2MB)
테스트 9 〉	통과 (143.20ms, 10.2MB)
테스트 10 〉	통과 (170.25ms, 10.2MB)
테스트 11 〉	실패 (시간 초과)
테스트 12 〉	통과 (0.01ms, 10MB)
테스트 13 〉	통과 (0.01ms, 10.3MB)
테스트 14 〉	통과 (4.56ms, 10.5MB)
테스트 15 〉	통과 (0.16ms, 10.2MB)
테스트 16 〉	통과 (0.33ms, 10.3MB)

---

3차 시도

접근 방법

1. 최단거리이므로 모든 경우의 수를 탐색하는 dfs보다 bfs가 적합하다. 

2. y == x 일 경우 0을 리턴한다. 

시간복잡도

큐에 들어가는 숫자의 개수는 O(y - x) 범위 내에 있으며, 각 숫자에 대해 최대 3가지 연산을 큐에 넣을 수 있으므로, 전체 시간 복잡도는 O(3 * (y - x))가 된다.
따라서 최종 시간 복잡도는 O(3 * (y - x)) = O(y - x)라고 볼 수 있다.

코드

from collections import deque

def solution(x, y, n):
    
    if y == x:
        return 0
    
    answer = int(1e9)
    
    q = deque()
    q.append((y, 0))
    
    while q:
        num, cnt = q.popleft()

        if num == x:
            answer = min(answer, cnt)
        
        if num < x or cnt > answer:
            continue
        
        if num - n >= x:
            q.append((num - n, cnt + 1))
        
        if num % 3 == 0:
            q.append((num // 3, cnt + 1))

        if num % 2 == 0:
            q.append((num // 2, cnt + 1))
            
    if answer == int(1e9):
        return -1 
    
    return answer

 

결과 : 정답

테스트 1 〉	통과 (0.01ms, 10MB)
테스트 2 〉	통과 (0.01ms, 10.2MB)
테스트 3 〉	통과 (0.00ms, 10.1MB)
테스트 4 〉	통과 (0.00ms, 10.1MB)
테스트 5 〉	통과 (50.24ms, 16MB)
테스트 6 〉	통과 (0.00ms, 10.1MB)
테스트 7 〉	통과 (43.10ms, 13.3MB)
테스트 8 〉	통과 (0.01ms, 10.1MB)
테스트 9 〉	통과 (143.74ms, 25.8MB)
테스트 10 〉	통과 (171.93ms, 29.1MB)
테스트 11 〉	통과 (57.29ms, 15.8MB)
테스트 12 〉	통과 (0.01ms, 10.2MB)
테스트 13 〉	통과 (0.01ms, 10.4MB)
테스트 14 〉	통과 (1.76ms, 10.3MB)
테스트 15 〉	통과 (0.12ms, 10.1MB)
테스트 16 〉	통과 (0.45ms, 10MB)

---

4차 시도

접근 방법

이미 계산한 숫자는 추가로 계산하지 않도록 방문 체크 딕셔너리를 이용하였다. 

 

코드

from collections import deque, defaultdict

def solution(x, y, n):
    
    if y == x:
        return 0
    
    answer = int(1e9)
    visited = defaultdict(bool)
    
    q = deque()
    q.append((y, 0))
    
    while q:
        num, cnt = q.popleft()
        
        if num == x:
            answer = min(answer, cnt)
        
        if num < x or cnt > answer:
            continue
        
        if num - n >= x and not visited[num - n]:
            q.append((num - n, cnt + 1))
            visited[num - n] = True 
        
        if num % 3 == 0 and not visited[num // 3]:
            q.append((num // 3, cnt + 1))
            visited[num // 3] = True 

        if num % 2 == 0 and not visited[num // 2]:
            q.append((num // 2, cnt + 1))
            visited[num // 2] = True 
            
    if answer == int(1e9):
        return -1 
    
    return answer

 

결과 : 정답

테스트 1 〉	통과 (0.01ms, 10.3MB)
테스트 2 〉	통과 (0.01ms, 10MB)
테스트 3 〉	통과 (0.01ms, 10.4MB)
테스트 4 〉	통과 (0.01ms, 10.2MB)
테스트 5 〉	통과 (0.37ms, 10.1MB)
테스트 6 〉	통과 (0.00ms, 10MB)
테스트 7 〉	통과 (0.62ms, 10.4MB)
테스트 8 〉	통과 (0.01ms, 10.3MB)
테스트 9 〉	통과 (0.53ms, 10.2MB)
테스트 10 〉	통과 (0.57ms, 10.3MB)
테스트 11 〉	통과 (1.05ms, 10.4MB)
테스트 12 〉	통과 (0.01ms, 10MB)
테스트 13 〉	통과 (0.01ms, 10.4MB)
테스트 14 〉	통과 (0.36ms, 10.2MB)
테스트 15 〉	통과 (0.07ms, 10.1MB)
테스트 16 〉	통과 (0.08ms, 10.2MB)

 

테스트 9의 경우 (143.74ms, 25.8MB) -> (0.53ms, 10.2MB) 로 엄청 시간이 줄어들었다! 

정리

---

최단 거리를 찾을 때는 BFS, 모든 경우의 수를 봐야 할 때는 DFS를 이용하자