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

https://programmers.co.kr/learn/courses/30/lessons/76503

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

import java.util.ArrayList;
import java.util.Arrays;
import java.util.LinkedList;
import java.util.List;
import java.util.Queue;
class Solution {
		public long solution(int[] a, int[][] edges) {
			long answer = 0;
			
			int link[] = new int[a.length]; //진입차수 갯수 
			Queue<Integer> queue = new LinkedList<>(); //진입차수 1인 정점 넣을 큐
			boolean[] visited = new boolean[a.length]; //방문체크
			List<Integer>[] list = new List[a.length]; //연결정보 담고 있는 리스트
			long[] b = new long[a.length]; //a배열을 담아줄 long 형 배열
			
			for (int i = 0; i < a.length; i++) { //b배열과 list초기화
				b[i] = a[i];
				list[i] = new ArrayList<>();
			}


			for (int i = 0; i < edges.length; i++) { //진입차수, list연결정보
				int start = edges[i][0];
				int end = edges[i][1];

				list[start].add(end);
				list[end].add(start);
				link[start]++;
				link[end]++;
			}

			for (int i = 0; i < a.length; i++) {
				int size = list[i].size();
				if (size == 1) {
					if (a[i] == 0) visited[i] = true; //진입차수가 1이고, a의 값이 0이라면 방문체크 하고 skip
					else queue.offer(i); //진입차수가 1인데 a의 값이 0이 아니면 큐에 삽입
				}
			}

			while (!queue.isEmpty()) {
				int no = queue.poll(); //진입차수가 1인 정점의 번호 
				visited[no] = true; //방문체크

				for (int i = 0; i < list[no].size(); i++) {
					int compareNodeNo = list[no].get(i); //비교할 정점 
					if (visited[compareNodeNo]) continue;
				
					answer += Math.abs(b[no]); //answer 양수로 더해주기
					b[compareNodeNo] += b[no];
					b[no] = 0; // 나 자신은 0
					if (--link[compareNodeNo] == 1) queue.add(compareNodeNo); //진입차수 1이면 큐 삽입
					break; //하나만 하면 되기 때문에 끝내주기
				}
			}
			answer = Arrays.stream(b).sum()==0 ? answer : -1; 
			return answer;
		}
	}

소요시간 : 1시간 10분

 

문제를 해석할 때 어디에도 이진트리라고 안적혀있고 그냥 트리라고 적혀있었는데, 저 혼자 이진트리네? 하고 생각하고 풀어서 시간이 좀 걸린 문제입니다

 

우선 사용한 변수는 이러합니다.

 

로직을 살펴보면 위상정렬과 유사합니다.

 

우선 처음 queue에는 진입차수가 1이고, a배열의 값이 0이 아닌

즉 리프노드이면서 값이 0이 아닌 노드만 큐에 삽입됩니다.

 

1. 큐에서 노드를 하나 뺀다. (현재노드)

2. 노드의 방문체크를 한다.

3. 이 노드와 연결된 노드 중 방문하지 않은 노드(비교노드)를 찾는다.

4. 비교노드에 현재노드의 값을 더해준다. 

5. 현재노드를 0을 만들어준다.

6. 마지막으로 배열이 0인지 아닌지 체크해 준다.

 

끝~