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

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

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

모든 경우의 수를 리스트에 담아서 계속 결과를 이어갔다. 

중복된 결과가 리스트에 담겨서 구현했을 시 시간초과를 예상했지만 시간초과는 나지 않았다. 

Set 으로 구현하는게 맞는 것 같다. 밑에는 수정 전 코드 => 리스트를 Set으로 바꿔주어야한다.

문제 분류인 dp하고는 맞지 않는것 같다

import java.util.*;
class Solution {
    public static ArrayList<Integer> adj[];
    
    public static int solution(int N, int number) {
        adj = new ArrayList[9];
        for(int i=0;i<9;i++){
            adj[i] = new ArrayList<Integer>();
        }
        if(N == number) return 1;
        int ret = 1;
        adj[1].add(N);
        while(true){
            ret++;
            if(ret > 8) return -1;
            //sb => 문자열 n을 이어붙인 것
            StringBuilder sb = new StringBuilder();
            for(int i=0;i<ret;i++){
                sb.append(N);
            }
            adj[ret].add(Integer.parseInt(sb.toString()));
            if(Integer.parseInt(sb.toString()) == number) return ret;
            for(int i=1;i<ret;i++){
                int s = i;
                int e = ret-i;
                for(int j=0;j<adj[s].size();j++){
                    for(int k=0;k<adj[e].size();k++){
                        int next1 = adj[s].get(j) + adj[e].get(k);
                        int next2= adj[s].get(j) * adj[e].get(k);
                        int next3 = Integer.MAX_VALUE;
                        if(adj[e].get(k) != 0)
                            next3 = adj[s].get(j) / adj[e].get(k);
                        int next4= adj[s].get(j) - adj[e].get(k);
                        adj[ret].add(next1);
                        adj[ret].add(next2);
                        if(next3!=Integer.MAX_VALUE)
                            adj[ret].add(next3);
                        adj[ret].add(next4);
                        if(next1 == number || next2 == number || next3 == number || next4 == number)
                            return ret;
                    }
                }
            }
        }
    }
}