[프로그래머스 - JAVA] 모두 0으로 만들기

문제 링크

• 모두 0으로 만들기

풀이

• 먼저 a의 길이가 최대 30만까지 가능하기 때문에 완전 탐색 대신 효율적 방법으로 풀어야 함을 알게 되었다.
• 문제 설명과 그림을 보면서 두 가지를 가정해보았다. 첫째는 모든 가중치의 합이 0인 경우에만 횟수를 구할 수 있다는 점이다. 둘째는 말단 노드에서 중심부 방향으로 처리를 하면 최소 횟수로 구할 수 있다는 점이다.
• 이미 방문한 노드는 remove()로 처리하고 싶었지만, a가 너무 크기 때문에 ArrayList, LinkedList 모두 시간 초과가 예상되었다. 그래서indegree[next] > 0로 방문 노드를 처리해주었다.
  • ArrayList의 remove 시간 복잡도는 O(n)이다.
  • LinkedList의 remove 시간 복잡도는 O(1)이지만, 조회 시 시간 복잡도가 O(n)이다.

코드

import java.util.*;

class Solution {
    public long solution(int[] a, int[][] edges) {
        if (!isPossible(a)) {
            return -1;
        }
        
        long answer = 0;
        int len = a.length;
        ArrayList<ArrayList<Integer>> graph = createGraph(len);
        int[] indegree = new int[len];
        long[] numbers = new long[len];
        for (int i = 0; i < len; i++) {
            numbers[i] = a[i];
        }
        for (int[] e : edges) {
            graph.get(e[0]).add(e[1]);
            graph.get(e[1]).add(e[0]);
            indegree[e[0]]++;
            indegree[e[1]]++;
        }
        
        Queue<Integer> que = new LinkedList<>();
        for (int node = 0; node < len; node++) {
            if (indegree[node] == 1) {
                que.offer(node);
            }
        }
        
        while (!que.isEmpty()) {
            // for (int i = 0; i < len; i++) {
            //     System.out.print(indegree[i] + " ");
            // }
            // System.out.println();
            int current = que.poll();
            long cost = numbers[current];
            indegree[current]--;
            answer += Math.abs(cost);
            numbers[current] = 0;
            
            for (int next : graph.get(current)) {
                if (indegree[next] > 0) {
                    indegree[next]--;
                    numbers[next] += cost;
                    
                    if (indegree[next] == 1) {
                        que.offer(next);
                    }
                    
                    break;
                }
            
            }
        }
        
        return answer;
    }
    
    private ArrayList<ArrayList<Integer>> createGraph(int len) {
        ArrayList<ArrayList<Integer>> graph = new ArrayList<>();
        
        for (int i = 0; i < len; i++) {
            graph.add(new ArrayList<>());
        }
        
        return graph;
    }
    
    private boolean isPossible(int[] numbers) {
        long sum = 0;
        for (int i : numbers) {
            sum += i;
        }
        
        if (sum == 0) {
            return true;
        } else {
            return false;
        }
    }
}