[2023 KAKAO BLIND RECRUITMENT] 1, 2, 3 떨어뜨리기 - java

문제 해결 전략

1. "어떤 숫자블록을 내릴 것인지를 제쳐두고" 어떤 리프노드에 도착할 것인지를 파악하기.
2. 도착한 리프노드의 "순서"와 "개수"를 저장하기
   • 도착한 리프노드의 개수와 target 배열과 비교하여 가능 여부 판단하기
     •  불가능하거나 가능하다면 반복문 종료 ( 도착한 해당 리프노드의 개수가 N이라고 할때 N <= target <= 3 *N을 만족해야한다.)
     • 가능 여부가 판정되지 않았다면 2.로 돌아가서 반복
3. 저장한 리프노드의 순서와 개수를 target과 비교해서 answer에 저장해야하는 숫자블록 구현하기
   • ex) target = 4, 리프노드의 개수 = 2 -> [1, 3]이 문제에서 요구하는 답. //// [2, 2] (x) / [3, 1](x)

3번을 구현할때 간결하게 구현할 수 있는 방법을 고민했다.

target이 7이고 숫자블록을 3번써서 만들어야 하는 경우를 구해야할때,

 

1. 해당 칸 _ _ _에 먼저 다 1을 채운다. 1 1 1

2. target - (빈칸을 채운 1의 개수) => remain을 구한다. 7 - 3 = 4

3. 반복문을 돌면서 remain이 2이상 일때 가장 뒷 자리부터 +2를 하고 remain을 2감소시킨다. 1 1 3, remain=2

4. 1 3 3, remain = 0

5. remain이 0이되면 반복문 종료

 

(만약 remain이 1이라면 해당 자리수를 +1증가시키고 remain을 1 감소 시킨다.)

 

해당 방법으로 숫자블록을 구해 answer에 넣어주었다.

import java.util.*;
class Solution{
	List<Integer>[] graph;
    List<Integer> order;  //도착한 리프노드 순서
    int[] count;          //도착한 리프노드 개수 저장

    public int[] solution(int[][] edges, int[] target) {
        graph = new List[target.length];
        count = new int[target.length];
        order = new ArrayList<>();
        for(int i=0; i<target.length; i++){
            graph[i] = new LinkedList<>();
        }
        for(int[] edge: edges){
            graph[edge[0]-1].add(edge[1]-1);
        }
        for(int i=0; i<graph.length; i++){
            Collections.sort(graph[i]);
        }

        //결과 존재 여부 파악 / -1: 불가능, 0: 아직 모름, 1: 가능
        int flag = 0;
        while(flag == 0){
            //이번 턴에 찾아진 리프노드
            int leafNode = findLeaf();

            count[leafNode]++;
            order.add(leafNode);

            flag = isPossible(target);
        }
        if(flag == -1) return new int[]{-1};

        //노드가 몇번째 인덱스에서 출현하는지 저장
        List<Integer>[] orderIndex = new List[target.length];
        for(int i=0; i<orderIndex.length; i++){
            orderIndex[i] = new ArrayList();
        }
        for(int i=0; i<order.size(); i++){
            int leafNode = order.get(i);
            orderIndex[leafNode].add(i);
        }

        int[] answer = new int[order.size()];

        for(int i=0; i<target.length; i++){
            //블록을 보내는 순서
            int[] blocks = calculate(target[i], count[i]);
            for(int j=0; j<blocks.length; j++){
                answer[orderIndex[i].get(j)] = blocks[j];
            }
        }
        return answer;
    }

    int findLeaf(){
        int node = 0;
        while(!graph[node].isEmpty()){
            int nxt = graph[node].get(0);
            graph[node].remove(0);
            graph[node].add(nxt);
            node = nxt;
        }
        return node;
    }

    int isPossible(int[] target){
        for(int i=0; i<count.length; i++){
            if(target[i] == 0 && count[i] > 0) return -1;
            if(target[i] != 0 && target[i] < count[i]) return -1;
            if(target[i] > 0 && target[i] > count[i] * 3) return 0;
        }
        return 1;
    }

    int[] calculate(int target, int count){
        int[] blocks = new int[count];
        Arrays.fill(blocks, 0, blocks.length, 1);

        int remain = target - count;
        int idx = blocks.length - 1;
        while(remain != 0){
            if(remain >= 2){
                blocks[idx] += 2;
                remain -= 2;
            } else{
                blocks[idx] += 1;
                remain -= 1;
            }
            idx = (idx - 1 + blocks.length) % blocks.length;
        }
        return blocks;
    }

}