프로그래머스 Lv.3) N으로 표현 (DP)

N으로 표현

코딩테스트 연습 - N으로 표현

풀이

 

고득점 Kit의 DP에 있는 문제다. 예전에 풀었을 때, DP로 풀지 않고 DFS로 풀었기 때문에 DP로 풀고자 했지만, 실패했다.

그래서 검색을 해봤더니 4중 for문을 돌리면서 답을 찾는 글들만 보였다.

좌표를 탐색하는 시뮬레이션 문제가 아닌 이상은, 4중 for문이 가독성이 더 떨어지고 이해하기 힘들다는 주관적인 의견이다.

물론, 머리가 좋으신 분들은 이해하시는데 문제가 없겠지만, 나같은 사람들이 범접할 수 있는 영역이 아닌 것 같았다.

 

DFS의 방법은 만들 수 있는 모든 수를 가지고 4칙 연산을 진행하는 것이다.

문제의 조건에 따라 문자 N 사용 횟수가 8이 넘어가면 -1을 반환하기 때문에, DFS가 가능했다.

또한, cnt가 8회가 넘을 경우에는 그냥 로직을 종료시켰다.

 

for문에 1부터 8-cnt를 주어, 남은 횟수까지만 N을 붙일 수 있도록 설정했다.

그리고, 1~8-cnt개의 N을 가지고 사칙연산을 진행한다. ( i = 1~ 8-cnt   => Digit(자릿 수)가 된다.)

덧셈, 뺄셈, 나눗셈, 곱셈이 진행된다.

코드 1의 increaseNum 이나 코드 2의 getNum은 N을 i개 만큼 붙인 수가 된다. ( 5, 55, 555 와 같은 숫자)

이 숫자들을 가지고 최소 횟수를 구해준다.

 

코드 1에서는 모든 결과값을 ArrayList에 담고 모든 탐색이 끝난 후, 9를 더해주어 정렬했을 때 9가 가장 적은 횟수라면 -1을 아니라면 가장 적은 횟수를 리턴해준다.

 

코드 2에서는 하나의 답이 나올 때마다, Min을 체크해줘서 최솟값을 직접 구했다. 후에 이 최솟값이 9로 변하지 않았을 때, -1을 리턴해주었다. 코드 1에 비해 가독성과 효율성이 더 좋다는 것에 만족하지만, DP로 못풀었다는 점과, DFS로 한번에 풀지 못하고 이전 코드를 참고했다는 점이 많이 아쉬웠다.

 

코드 1

 

import java.util.ArrayList;
import java.util.Collections;

class Solution {
    static ArrayList<Integer> cntList;
    
    public int solution(int N, int number) {
        cntList = new ArrayList<>();
        dfs(0, 0, N, number);
        cntList.add(9);
        Collections.sort(cntList);

        int answer = cntList.get(0);

        return answer > 8 ? -1 :answer;
    }
    
    private static void dfs(int cnt, int number, int N, int target) {
        if(cnt >8) {
            return;
        }
        if(number == target) {
            cntList.add(cnt);
            return;
        }
        for(int i=1; i<=8-cnt; i++) {
            dfs(cnt + i, calculator(0, number, increaseNum(i,N)), N, target);
            dfs(cnt + i, calculator(1, number, increaseNum(i,N)), N, target);
            dfs(cnt + i, calculator(2, number, increaseNum(i,N)), N, target);
            dfs(cnt + i, calculator(3, number, increaseNum(i,N)), N, target);
        }
    }

    private static int increaseNum(int digit, int N) {
        int result = 0;
        for(int i=0; i<digit; i++) {
            result += Math.pow(10,i)*N;
        }
        return result;
    }
    
    private static int calculator(int cmd, int left, int right) {
        int result =0;

        switch (cmd) {
            case 0: // 덧셈
                result = left + right;
                break;
            case 1: // 뺄셈
                result = left - right;
                break;
            case 2: // 곱셈
                result = left * right;
                break;
            case 3: // 나눗셈
                result = right ==0 ? 0 :left / right;
                break;
            case 4: // 자기 자신 두자릿수
                result = left*10 + left;
                break;
            default:
                break;
        }

        return result;
    }

    private static int getDigit(int num) {  // 자리 수 구하기
        int cnt =1;

        while(num /10 !=0) {
            cnt++;
            num /=10;
        }
        return cnt;
    }
}

 

코드 2

 

class Solution {
    int answer;
    public int solution(int N, int number) {
        answer = 9;
        dfs(0, 0, N, number);
        return answer > 8 ? -1 : answer;
    }
    
    private void dfs(int cnt, int number, int N, int target) {
        if(cnt >8) {
            return;
        }
        if(number == target) {
            answer = Math.min(answer, cnt);
            return;
        }
        
        for(int i=1; i<=8-cnt; i++) {   // digit
            dfs(cnt+i, number+getNum(i,N), N, target);
            dfs(cnt+i, number-getNum(i,N), N, target);
            dfs(cnt+i, number/getNum(i,N), N, target);
            dfs(cnt+i, number*getNum(i,N), N, target);
        }
    }
    private int getNum(int digit, int N) {
        int result =0;
        for(int i=0; i<digit; i++) {
            result += Math.pow(10,i)*N;
        }
        return result;
    }
}