[프로그래머스/Java] 1,2,3 떨어트리기

---

문제

https://school.programmers.co.kr/learn/courses/30/lessons/150364

프로그래머스

 

---

문제 풀이

해당 문제는 특정 알고리즘 문제가 아닌 구현 문제로 판단하여 모든 기능을 차례대로 구현했다.

그 과정에서 숫자를 어떤 순서로 내려야하는지 많은 고민을 했다. 결과만 말하자면 계속 임의의 수를 내려보내 받은 숫자의 개수를 저장하고, 이를 target 숫자를 만들수 있냐 없냐로 분기처리하였다.

 

우리가 떨어뜨릴 수 있는 숫자는 1,2,3밖에 없으므로 아래와 같은 공식으로 모든 노드가 target 값을 만들 수 있는지를 숫자를 떨어뜨릴 때마다 체크해야 한다.

 

현재 노드가 보유하고 있는 숫자 개수 ≤ 노드의 target 값 ≤ 현재 노드가 보유하고 있는 숫자 개수 * 3

 

따라서, target 값대로 리프 노드에 숫자를 쌓을 수 있는지 확인하려면 다음과 같은 과정을 거쳐야 합니다.

 

1. 트리에 숫자를 떨어뜨린다.
2. 각 리프 노드에 숫자가 몇 개씩 떨어졌는지 카운팅한다.
3. 현재까지 떨어뜨린 숫자의 개수로 모든 리프 노드에서 target 값을 만들 수 있는지를 위의 공식을 통해 확인한다.
4. 만약 모든 리프 노드의 target 값을 만들 수 있다면 루프를 탈출합니다. 이때가 가장 적은 숫자를 사용하여 target 값대로 리프 노드에 숫자를 쌓을 수 있는 때이다. target 값을 만들 수 없는 리프 노드가 하나라도 있다면 (1.)로 돌아간다.

 

단, target을 만들 수 없는 트리가 입력으로 주어졌다면, 위 과정에서 무한 루프를 돌 수 있다. 어떤 노드에서 현재까지 떨어뜨린 숫자로 target 값을 만들 수 없는 경우는 다음과 같이 2가지가 있다. 이 중에서 2번째 경우가 target을 만드는 것이 불가능한 트리가 주어진 경우이다. 

 

• 노드의 target 값 > 현재 노드가 보유하고 있는 숫자 개수 * 3인 경우는 현재 보유하고 있는 숫자 개수가 적어서 target 값을 만들 수 없는 경우이므로 숫자를 더 떨어트리면 target 값을 만들 수 있습니다.

 

• 현재 노드가 보유하고 있는 숫자 개수 > 노드의 target 값인 경우는 현재 보유하고 있는 숫자를 모두 1로 바꿔도 target을 만들 수 없습니다. 따라서 영원히 target대로 숫자의 합을 만들 수 없으므로, 더 이상 루프를 돌지 말고 [-1]을 return 해야 합니다.

 

여기까지가 target대로 숫자의 합을 만들 수 있는지 없는지를 구하고, 만들 수 있는 경우 사용하는 숫자의 최소 개수까지 구하는 과정이다.

 

---

문제 풀이 코드

import java.util.*;

class Solution {
    
    public static class Result{
        int no;
        String status;
        
        public Result(int no, String status){
            this.no = no;
            this.status = status;
        }
    }
    
    public static class Node implements Comparable<Node>{
        int no;
        ArrayList<Node> list = new ArrayList<>();
        int numCount = 0;
        ArrayList<Integer> countList = new ArrayList<>();
        ArrayList<Integer> numList = new ArrayList<>();
        
        int target;
        int route = 0;
        boolean isleap = true;
        

        public Node(int no, int target){
            this.no = no;
            this.target = target;
        }
        public void addChild(Node child){
            list.add(child);
        }
        
        public void startSet(){
            isleap = list.size() == 0;
            if(!isleap){
                list.sort(null);
                route = 0;
            }
        }
        
        public Result addNum(int num){
            if(isleap){
                if(numCount >= target){
                    return new Result(no,"over");
                }
                numCount++;
                countList.add(num);
                if(numCount <= target && numCount*3 >= target){
                    numList.clear();
                    for(int i = 0; i < numCount; i++){
                        numList.add(1);
                    }
                    int needNum = target - numCount;
                    for(int i = numCount-1; i >= 0; i--){
                        if(needNum == 0) break;
                        else if(needNum == 1){
                            numList.set(i,2);
                            break;
                        }else{
                            numList.set(i,3);
                            needNum -= 2;
                        }
                    }
                    System.out.println(numList);
                    return new Result(no,"possible");
                }
                return new Result(no,"less");
                
            }else{
                int temp = route;
                route = (route+1)%list.size();
                return list.get(temp).addNum(num);
            }
        }

        @Override
        public int compareTo(Node o){
            return this.no - o.no;
        }
    }
    
    public int[] solution(int[][] edges, int[] target) {
        Map<Integer,Node> memo = new HashMap<>();
        Node root = new Node(1,-1);
        memo.put(1,root);
        int sum = Arrays.stream(target).sum();
        
        for(int[] edge : edges){
            int parent = edge[0];
            int child = edge[1];
            
            if(!memo.containsKey(child)){
                memo.put(child,new Node(child,target[child-1]));
            }
            if(!memo.containsKey(parent)){
                memo.put(parent,new Node(parent,target[parent-1]));
            }
            memo.get(parent).addChild(memo.get(child));
            
        }
        
        for(int n : memo.keySet()){
            memo.get(n).startSet();
        }
        
        int count = 1;
        boolean[] statusBoard = new boolean[target.length];
        for(int i = 0 ; i < target.length; i++){
            if(target[i] == 0)statusBoard[i] = true;
        }
        boolean isComplete = true;
        while(true){
            Result result = root.addNum(count++);
            
            if(result.status == "over")break;
            
            if(result.status == "possible"){
                statusBoard[result.no-1] =true;
            }else{
                statusBoard[result.no-1] =false;
            }
            isComplete = true;
            for(boolean r : statusBoard){
                if(!r){
                    isComplete = false;
                    break;
                }
            }
            if(isComplete)break;
        }
        
        if(!isComplete) return new int[] {-1};
        
        ArrayList<Integer> answer = new ArrayList<>();
        
        for(int i = 1; i < count; i++){
            for(int x = 1; x <= target.length; x++){
                Node temp = memo.get(x);
                if(!temp.countList.contains(i))continue;
                answer.add(temp.numList.get(temp.countList.indexOf(i)));
                break;
            }
        }
        
        int[] answerArr = new int[answer.size()];
        for(int i = 0 ; i < answer.size(); i++){
            answerArr[i] = answer.get(i);
        }
            
        return answerArr;
    }
}