[Lv.3] 모두 0으로 만들기

6,7,8 런타임 오류 코드

import java.util.*;

class Solution {

    static boolean[] isChecked;
//    boolean[] isVisited;
    static long[] valueArr;
    static Map<Integer, List<Integer>> edgeMap;
    static long count;
    public long solution(int[] a, int[][] edges) {
        isChecked=new boolean[a.length];
//        isVisited=new boolean[a.length];
//        valueArr=a.clone();
        valueArr=new long[a.length];
        edgeMap=new HashMap<>();
        count=0;
        //한 노드 잡고  그 자식 노드들 싹 돌면서 값의 합을 현재 노드에 더하는 로직 구현.
        for (int i = 0; i < a.length; i++) {
            valueArr[i]=a[i];
            edgeMap.put(i,new ArrayList<>());
        }
        for (int i = 0; i < edges.length; i++) {
            int[] edge = edges[i];
            edgeMap.get(edge[0]).add(edge[1]);
            edgeMap.get(edge[1]).add(edge[0]);
        }
//        for (int i = 0; i < a.length; i++) {
//            if(!isChecked[i])
//                getAllKid(i);
//        }
        getAllKid(0);
//        System.out.println("count : "+count);
//        for (int i = 0; i < a.length; i++) {
//            if(valueArr[i]!=0){
//                return -1;
//            }
//        }
        if(valueArr[0]!=0){
            return -1;
        }
        return count;
    }

    private void getAllKid(int i) {
        //후위순회 형식으로 LR먼저 다 탐색하고 루트 돌아오면 LR값 전부 합친걸 현재 value에 더해줌
        //물론, count는 절댓값 취해서 더해줘야지
        isChecked[i]=true;
        boolean hasChild=false;
        long nowSum=0;
        long nowCount=0;
        for (int j = 0; j < edgeMap.get(i).size(); j++) {
            Integer edge = edgeMap.get(i).get(j);
            if (!isChecked[edge]) {
                getAllKid(edge);
                hasChild = true;
                nowSum += valueArr[edge];
                nowCount += Math.abs(valueArr[edge]);
                valueArr[edge] = 0L;
            }
        }
        if(hasChild){
            count+=nowCount;
            valueArr[i]+=nowSum;
        }
    }

}

그냥 후위순회라고 생각하고 풀면 쉽게 풀 수 있던 문제였다.

다만, 제한 사항 자체가 꽤 크기에 long을 사용해야 하고, 메모리 초과에 주의해야 했다.

 

그냥 위 코드처럼 edge들을 Map으로 받으니 계속해서 메모리 초과가 발생했다.

 

결국, 그냥 List array를 사용하게끔 코드를 조금 수정하니 바로 통과가 되었다..

 

정답코드

import java.util.*;

class Solution {

    static boolean[] isChecked;
    static long[] valueArr;
    List<Integer>[] edgeMap;
    static long count;
    public long solution(int[] a, int[][] edges) {
        isChecked=new boolean[a.length];
        valueArr=new long[a.length];
        edgeMap=new List[a.length];
        count=0;
        for (int i = 0; i < a.length; i++) {
            valueArr[i]=a[i];
            edgeMap[i]=new ArrayList<>();
        }
        for (int i = 0; i < edges.length; i++) {
            int[] edge = edges[i];
            edgeMap[edge[0]].add(edge[1]);
            edgeMap[edge[1]].add(edge[0]);
        }
        getAllKid(0);
        if(valueArr[0]!=0){
            return -1;
        }
        return count;
    }

    private void getAllKid(int i) {
        //후위순회 형식으로 LR먼저 다 탐색하고 루트 돌아오면 LR값 전부 합친걸 현재 value에 더해줌
        //물론, count는 절댓값 취해서 더해줘야지
        isChecked[i]=true;
        boolean hasChild=false;
        long nowSum=0;
        long nowCount=0;
        for (int j = 0; j < edgeMap[i].size(); j++) {
            Integer edge = edgeMap[i].get(j);
            if (!isChecked[edge]) {
                getAllKid(edge);
                hasChild = true;
                nowSum += valueArr[edge];
                nowCount += Math.abs(valueArr[edge]);
                valueArr[edge] = 0L;
            }
        }
        if(hasChild){
            count+=nowCount;
            valueArr[i]+=nowSum;
        }
    }

}