(알고리즘 스터디) 12주차 수_(Programmers) 숫자 변환하기

🌟 프로그래머스 / 연습문제 / Level 2 / 숫자 변환하기

📃 문제

프로그래머스

🚫 제한 사항

• 1 ≤ x ≤ y ≤ 1,000,000
• 1 ≤ n < y

👀 입출력 예

x	y	n	result
10	40	5	2
10	40	30	1
2	5	4	-1

🤔 풀이 방법

1️⃣ 생각 정리 (1) - PASS

➡️ x 에서 출발하여 y 를 만들기 까지의 경우를 크게 3가지로 나누어 볼 수 있다.

① Only 곱으로만
② Only 합으로만
③ 합 & 곱 모두 사용

➡️ 어느 숫자에 근접하기 좋은 방법은 아무래도 곱이지만 더하기에 제공된 n 이 생각보다 큰 수 일 때는 더하기가 더 효율적일 수 있다. 따라서 상황에 따라 결과를 비교할 필요가 있다.

2️⃣ 생각 정리 (2) - DFS

① 기본 아이디어

➡️ 생각해보니 x 에서 y 로 키워나가기 보다는 y 에서 x 로 줄여나가는 것이 합 & 곱을 생각하기 편할 것 같았다. 예시 2 를 그림으로 표현해보면,

➡️ 위와 같이 표현 가능한데, 거꾸로 내려갈 경우 %2, %3, -n 중에 가능한 연산이 바로 확인이 가능하므로 x 에서 y 로 키워나가는 것 보다 효율적으로 판단이 가능하다.

 

② 코드 작성

➡️ 위 아이디어는 DFS 라고 볼 수 있을 것 같다. 따라서 아래와 같이 함수를 생성하였다.

public static void dfs (int y, int depth, int calc) {

    // 부분 ①
    switch (calc) {
        case 0 :// %2
            if (y % 2 != 0) return;
            y /= 2;
            break;

        case 1 : // %3
            if (y % 3 != 0) return;
            y /= 3;
            break;

        case 2 : // - n
            if (y-nn < goal) return;
            y -= nn;
            break;
    }

    // 부분 ②
    if (y == goal) {
        if (answer > 0) {
            answer = Math.min(answer, depth);
            return;
        }
        answer = depth;
        return;
    }
    
    // 부분 ③
    dfs (y, depth+1, 0);
    dfs (y, depth+1, 1);
    dfs (y, depth+1, 2);
    return;
}

부분 ①
➡️ %2 / %3 / -n 중 어떤 연산을 해야하는지 확인하기 위해 switch 문을 사용하였다.
부분 ②
➡️ 연산 뒤에는 목표하는 값 (x) 와 변경된 값 y 가 같은지 확인하고, 같은 경우 기존 최소값과 비교하여 더 작은 값을 저장한다.
부분 ③
➡️ 변경된 값 y 가 목표하는 값 (x) 과 같지 않을 경우 다음 깊이로 들어간다.

③ 결과

➡️ 테스트 코드는 통과하였지만, 정확성 테스트를 실행시켜보면 시간 초과로 실패하는 케이스가 많이 있다. 생각해보니 x 와 y 간의 차이가 크면서 n 이 1 일 경우 DFS 를 실행하면 시간 관점에서 비효율적일 수 있을 것이라는 생각이 들었다.

 

④ 개선 (1)

➡️ 시간초과 문제를 해결하기 위해서 depth 가 answer 보다 깊게 들어가면 더 이상 연산을 진행하지 않고 종료하도록 코드를 추가하였다. 어처피 곱하기나 더하기가 몇 번 나오는지는 중요한 문제가 아니기 때문에 최소값만 확인하도록 하였다.

if (answer > 0 && depth >= answer) return;

➡️ 그 결과 시간초과로 실패했던 대부분의 테스트 케이스들을 통과할 수 있었다. 이제 6번과 11번 테스트의 실패 요인을 생각해보아야한다.

 

④ 개선 (2)

➡️ 6번이 틀리는 이유는 생각보다 단순했다. x == y 인 경우임으로 0 을 리턴해주면 된다.

if (x == y) return 0;

➡️ 11번만 통과하면 끝인데 개선점을 아직 더 찾지 못했다.

💻 풀이 코드

class Solution {
    public static int goal;
    public static int nn;
    public static int answer = -1;
    
    public int solution(int x, int y, int n) {
        // 정적 변수 초기화
        goal = x;
        nn = n;
        
        // 예외처리 : 두 수가 같을 경우
        if (x == y) return 0;
        
        dfs (y, 1, 0);
        dfs (y, 1, 1);
        dfs (y, 1, 2);
        
        return answer;
    }
    public static void dfs (int y, int depth, int calc) {
        
        // 최소값만을 확인함
        if (answer > 0 && depth >= answer) return;
        
        switch (calc) {
            case 0 :// %2
                if (y % 2 != 0) return;
                y /= 2;
                break;
            
            case 1 : // %3
                if (y % 3 != 0) return;
                y /= 3;
                break;
                
            case 2 : // - n
                if (y-nn < goal) return;
                y -= nn;
                break;
        }
        
        // 목표값에 도달한 경우
        if (y == goal) {
            if (answer > 0) {
                answer = Math.min(answer, depth);
                return;
            }
            answer = depth;
            return;
        }
        
        dfs (y, depth+1, 0);
        dfs (y, depth+1, 1);
        dfs (y, depth+1, 2);
        return;