[프로그래머스] [월간 코드 챌린지 시즌2] 모두 0으로 만들기 (JAVA)

0️⃣ 모두 0으로 만들기

 

지난 4월 15일 월간 코드 챌린지 3번 문제로 나왔던 "모두 0으로 만들기",

실제 시험 때는 못풀었었다. ㅠ 

 

해설을 보고 해결했는데, DFS로 트리의 leaf 노드부터 올라오면서 답을 구하는 방식이었다. 

실제 시험이 끝나고 오픈채팅방에서 이 방법으로 풀었다는 사람들이 몇 있었는데, 

이 방법이 이런 유형의 문제에 정형화된 풀이 방식으로 있는건가.. ?

ㅠㅠ 나는 몰랐는데.. 

 

---

문제 설명

 

각 점에 가중치가 부여된 트리가 주어집니다. 당신은 다음 연산을 통하여, 이 트리의 모든 점들의 가중치를 0으로 만들고자 합니다.

• 임의의 연결된 두 점을 골라서 한쪽은 1 증가시키고, 다른 한쪽은 1 감소시킵니다.

하지만, 모든 트리가 위의 행동을 통하여 모든 점들의 가중치를 0으로 만들 수 있는 것은 아닙니다. 당신은 주어진 트리에 대해서 해당 사항이 가능한지 판별하고, 만약 가능하다면 최소한의 행동을 통하여 모든 점들의 가중치를 0으로 만들고자 합니다.

트리의 각 점의 가중치를 의미하는 1차원 정수 배열 a와 트리의 간선 정보를 의미하는 edges가 매개변수로 주어집니다. 주어진 행동을 통해 트리의 모든 점들의 가중치를 0으로 만드는 것이 불가능하다면 -1을, 가능하다면 최소 몇 번만에 가능한지를 찾아 return 하도록 solution 함수를 완성해주세요. (만약 처음부터 트리의 모든 정점의 가중치가 0이라면, 0을 return 해야 합니다.)

 

 

제한 사항

• a의 길이는 2 이상 300,000 이하입니다.
  • a의 모든 수는 각각 -1,000,000 이상 1,000,000 이하입니다.
  • a[i]는 i번 정점의 가중치를 의미합니다.
• edges의 행의 개수는 (a의 길이 - 1)입니다.
  • edges의 각 행은 [u, v] 2개의 정수로 이루어져 있으며, 이는 u번 정점과 v번 정점이 간선으로 연결되어 있음을 의미합니다.
  • edges가 나타내는 그래프는 항상 트리로 주어집니다.

 

 

입출력 예

 

a	edges	result
[-5,0,2,1,2]	[[0,1],[3,4],[2,3],[0,3]]	9
[0,1,0]	[[0,1],[1,2]]	-1

 

---

💡  나의 풀이

import java.util.*;

class Solution {
    static int V;
    static long[] cost;
    static boolean[] visited;
    static List<Integer>[] children;
    static long count = 0;
    
    public long solution(int[] a, int[][] edges) {
        V = a.length;
        cost = new long[V];
        visited = new boolean[V]; 
        children = new ArrayList[V];
        
        long sum = 0;
        for(int i=0; i<V; i++) {
            sum += a[i];
            cost[i] = a[i];
            children[i] = new ArrayList<>();
        }
        
        if(sum != 0) return -1;
        
        for(int[] edge: edges) {
            int node1 = edge[0];
            int node2 = edge[1];
            children[node1].add(node2);
            children[node2].add(node1);
        }
        
        dfs(0);
        return count;
    }
    
    private long dfs(int cur) {
        visited[cur] = true;
        for(int i=0; i<children[cur].size(); i++) { //enhanced for loop 사용하면 런타임 에러 발생
            int next = children[cur].get(i);
            if(visited[next]) continue;
            cost[cur] += dfs(next);
        }
        count += Math.abs(cost[cur]);
        return cost[cur];
    }
}

 

 

그런데 38번 째 줄에서 enhanced for loop을 사용하면 테케 7,8에서 런타임 에러가 발생하고,

일반 for loop을 사용하면 AC를 받는다 .. 

 

enhanced for loop으로 인한 런타임에러인 것으로 보아 OOM인 것을 유추할 수 있다 ㅡ ㅡ;

출제자가 Java 메모리 제한을 너무 빡세게 둔 듯 하다. 

(그런데 이것도 서버 기분따라 통과하기도 한다고 함)

 

 

 

---

 

코딩테스트 연습 - 모두 0으로 만들기