[프로그래머스] N으로 표현(JAVA)

코딩테스트 연습(동적계획법) - N으로 표현

링크 : https://school.programmers.co.kr/learn/courses/30/lessons/42895

프로그래머스

문제 설명

모든 수는 어떤 수를 연속하여 쓰거나 사칙연산을 통해 만들 수 있다.

어떤수 N과 만들어야하는 수 number가 주어질 때 N으로 number를 만드려면 몇개의 N이 필요한지 구하는 문제이다.

위의 예제에서는 (55+5)/5 의 경우가 4개로 가장 적으므로 4를 출력한다.

문제 풀이

생각 과정

내가 생각한 방법은 우선 숫자와 그 숫자를 만들기위해 필요한 횟수를 저장하는 Number클래스를 하나 만든다.

그리고 큐를 이용하여 N에대해 사칙연산을 진행하며 큐에 넣어주고

큐에서 다시 숫자를 꺼내 사칙연산 과정을 반복한다. 원하는 숫자가 만들어지면 중지한다.

사칙연산 과정에서 중복방문이 생길 수 있으므로 방지해줘야한다.

 

이때 가장 작은 횟수를 구하기 위해 큐를 우선순위 큐로 생성해주고 compareTo를 Number클래스내에 오버라이드하여

횟수를 기준으로 비교하게 만든다.

그러면 적은 횟수 우선으로 사칙연산이 진행되게 된다.

 

그다음 또 생각해야할 부분이 숫자를 연속으로 쓸 수 있다는 점이다. 5뿐아니라 55, 555... 도 사용이 가능하다는건데

이를 해결하기위해 만들 수 있는 연속수를 모두 리스트에 저장한 후 모든 연속수에대해 사칙연산을 진행한다.

(이 부분에서 고민을 많이했는데 아래 주의점에서 다시 이야기해보겠다.)

 

구현

import java.util.*;

class Solution {
    static List<Number> list;
    static boolean[] visit;

    public int solution(int N, int number) {
        int answer = Integer.MAX_VALUE;
        visit = new boolean[1000001];    // 중복방지
        list = new ArrayList<>();   // 해당숫자로 만들 수 있는 기본 숫자 리스트 {5,55,555,5555,...}
        String s = String.valueOf(N);
        int c = 1;
        int f = N;
        while (f < 1000000) {	// 리스트를 연속수로 채우기
            list.add(new Number(f,c++));
            visit[f] = true;
            f=f*10+N;
        }

        Queue<Number> q = new PriorityQueue<>();  //우선순위 큐로 설정하여 원하는 최솟값찾기
        q.addAll(list);
       
        while(!q.isEmpty()){	 // 큐에 계산 결과 넣으면서 원하는 값 찾기
            Number cur = q.poll();
            visit[cur.num] = true;
            if (cur.num == number) {
                if (cur.cnt > 8) return -1;
                return cur.cnt;
            }
            for (int i = 0; i < list.size(); i++) {
                int next = 0;
                for (int j = 0; j < 6; j++) {
                    if (j==5 && cur.num==0) continue;   // 0으로 나눌 수 없음
                    if (j==3 && list.get(i).num==0) continue;   // 0으로 나눌 수 없음
                    next = cal(cur.num, list.get(i).num,j); // 계산 결과
                    if (next>= visit.length || next<0 || visit[next]) continue; // 범위 밖or이미 방문

                    q.add(new Number(next, cur.cnt + i+1));
                }
            }
        }
        return 0;
    }

    private int cal(int num, int num1, int j) {     // 계산
        if (j==0) return num + num1;
        if (j==1) return num - num1;
        if (j==2) return num * num1;
        if (j==3) return num / num1;
        if (j==4) return num1 - num;
        if (j==5) return num1 / num;
        return 0;
    }

    public static class Number implements Comparable<Number>{   // 숫자와 필요한 횟수를 저장
        int num;
        int cnt;

        public Number(int num, int cnt) {
            this.num = num;
            this.cnt = cnt;
        }

        @Override
        public int compareTo(Number o) {
            return this.cnt-o.cnt;
        }
    }
}

주의점

연속수를 만드는 부분에서 몇까지 만들어야하나 고민을 많이 했다. 

주어진 조건에서 number는 32000이하이고 횟수가 8을 넘어가면 -1을 출력하도록 되어있다.

 

가장 큰 9를 기준으로 봤을 때 9를 6개 사용한 연속수의 경우 999,999 이고 이 숫자에 가장 큰 변화를 주려면 곱하거나 나누는 경우가 있을 것이다. 그러나 곱하는 것은 이미 32000을 넘어가서 범위 밖이므로 생각하지 않고 나누는 경우를 생각하면 되는데

999,999/99 의 경우가 8개를 모두 사용한 경우이다. 이 결과값은 12,345 이다. number의 범위 안으로 들어오게되므로 6자리 연속수는 충분히 생각해야할 범위이다.

그러나 7자리의 연속수를 보면 9,999,999 이고 이를 number 범위 안으로 만드려면 최소 999를 나눠야하는데 그렇게 되면 9의 사용횟수가 10이 되므로 -1을 출력한다. 따라서 7자리,8자리...그 이상의 연속수들은 모두 횟수가 8을 넘어 -1을 리턴하므로 생각해줄 필요가 없다.

 

따라서 나의 풀이에선 연속수를 1,000,000 이하의 숫자로 생성해줬다.

---

다른 사람의 풀이를 보고 해당 방법도 좋은 것 같아 그 방식으로 다시 풀이해봤다.

Set과 배열을 이용한 방법이다.

import java.util.HashSet;
import java.util.Set;

class Solution {
    static Set<Integer>[] setArr;
    public int solution(int N, int number) {
        int answer = -1;
        setArr = new Set[9];    // 각 사용횟수마다 저장할 Set배열
        int f = N;
        for(int i = 1; i < 9; i++) {    // 연속수를 횟수에 따라 저장한다.
            setArr[i] = new HashSet<>();
            setArr[i].add(f);
            f = f * 10 + N;
        }
        for(int i = 1; i < 9; i++) {    
            for(int j = 1; j < i; j++) {
                cal(i,j);   // 사칙연산
            }
        }
        for(int i = 1; i < 9; i++) {
            if(setArr[i].contains(number)) {    // 낮은 횟수부터 number를 만들었는지 확인
                answer = i;
                break;
            }
        }
        return answer;
    }
    
    public static void cal(int i, int j){
        for(Integer a : setArr[j]) {
            for(Integer b : setArr[i - j]) {
                setArr[i].add(a + b);
                setArr[i].add(a - b);
                setArr[i].add(b - a);
                setArr[i].add(a * b);
                if(b != 0) {
                    setArr[i].add(a / b);
                }
                if(a != 0) {
                    setArr[i].add(b / a);
                }
            }
        }
    }
}

이 방법은 각 횟수마다 만들 수 있는 수를 Set배열에 저장하는 것이다.

그리고 그 Set배열을 각각 돌면서 다시 사칙연산을 해주는 방법이다.

내 방법과의 차이는 나는 우선순위 큐를 사용하여 낮은 횟수부터 계산을 진행하기 때문에 원하는 number가 나오면 무조건

최소 횟수이므로 중지하고 출력하면되지만 

두번째로 작성한 방법은 최소횟수부터 진행하는 것이 아니므로 모든 경우를 다 구한 후 낮은 횟수부터 원하는 number가 포함되어있는지 확인해봐야한다.