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

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

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

import java.util.*;

class Solution {
    static Map<Integer, Integer> map=new HashMap<>();
    static ArrayList<ArrayList<Integer>> list=new ArrayList<>();
    public int solution(int N, int number) {
        int answer = 0;
        list.add(new ArrayList<>());
        for (int i=1; i<=8; i++){
            list.add(new ArrayList<>()); 
            int num=makeNum(i, N);
            if (!map.containsKey(num)){
                map.put(num, i);
                list.get(i).add(num);
            }
            for (int j=1; j<i; j++){
                int a=j;        //a번(j개 이용)+b번(i-j개 이용)=i번
                int b=i-j;
                check(a, b, i);
            }
        }
        return map.containsKey(number)? map.get(number):-1;
    }
    private void check(int a, int b, int tot){
        int res;
        for (int i=0; i<list.get(a).size(); i++){
            for (int j=0; j<list.get(b).size(); j++){
                int num1=list.get(a).get(i);
                int num2=list.get(b).get(j);
                res=num1+num2;
                insert(res, tot);
                res=num1-num2;
                insert(res, tot);
                res=num1*num2;
                insert(res, tot);
                if (num1%num2==0){
                    insert(num1/num2, tot);
                }
            }
        }
    }
    private void insert(int res, int tot){
        if (res>0 && !map.containsKey(res)){
            map.put(res, tot);
            list.get(tot).add(res);
        }
    }
    
    private int makeNum(int it, int N){
        int num=0;
        int mul=1;
        for (int i=0; i<it; i++){
            num+=(N*mul);
            mul*=10;
        }
        return num;
    }
}

아이디어를 떠올리기 어려웠던 문제

 

이 문제의 포인트는

1개로 만들 수 있는 숫자

2개로 만들 수 있는 숫자(2개 단독, 1개+1개)

3개로 만들 수 있는 숫자(3개 단독, 1개+2개, 2개+1개 ..)

4개로 만들 수 있는 숫자(4개 단독, 1개+3개, 2개+2개, 3개+1개) 

...

를 구해주는 것이다.

 

나는 n개로 만들 수 있는 숫자에는 arraylist를 썼고,

각 숫자와 그 숫자를 만들기 위해 필요한 최소 갯수를 저장하기 위해서 map을 이용했다.

 

근데 이렇게 2개의 자료구조를 쓸 필요 없이,

set으로 n개로 만들 수 있는 숫자를 저장한 후 (즉 8개의 set이 만들어진다)

각 set을 매칭시켜서 값을 구한 후 해당 set에 답이 들어있는지 체크하고 답이 들어있으면 그 답을 return 해주면 된다.