[프로그래머스] 2021 카카오/ 매출 하락 최소화 (Java)

#7 매출 하락 최소화

2021 카카오 블라인드

난이도 : LEVEL 4

유형 : 트리 순회 / DP 

코딩테스트 연습 - 매출 하락 최소화

[문제]

직원들의 하루평균 매출액 값을 담은 배열 sales, 직원들의 팀장-팀원의 관계를 나타내는 2차원 배열 links가 매개변수로 주어집니다. 이때, 모든 팀에서 최소 한 명 이상 워크숍에 참석하면서, 참석하는 직원들의 하루평균 매출액의 합을 최소로 하려고 합니다. 그렇게 최소화된 매출액의 합을 구해서 return 하도록 solution 함수를 완성해 주세요.

 

[제한사항]

• sales 배열의 크기는 2 이상 300,000 이하입니다. sales 배열의 크기는 CEO를 포함한 전체 직원 수와 같습니다.
  • sales 배열은 각 직원들의 하루평균 매출액을 담고 있으며, 1번 직원부터 직원번호 순서대로 주어집니다.
  • sales 배열의 각 원소의 값은 0 이상 10,000 이하인 정수입니다.
• links 배열의 크기는 sales 배열의 크기 - 1 입니다. 즉, 전체 직원 수보다 1이 작습니다.
• links 배열의 각 원소는 [a, b] 형식입니다.
  • a는 팀장의 직원번호, b는 a팀장이 관리하는 팀원의 직원번호이며, a와 b는 서로 다른 자연수입니다.
  • 1 ≤ a ≤ sales 배열의 크기 입니다.
  • 2 ≤ b ≤ sales 배열의 크기 입니다.
  • 직원번호 1은 CEO로 정해져 있고 CEO는 항상 팀장으므로 b ≠ 1 입니다.
  • links 배열로 만들어지는 조직도는 하나의 트리 구조 형태입니다.
• 정답으로 return 되는 값은 2^31 - 1 이하인 자연수임이 보장됩니다.

 

문제 풀이 

트리 구조를 탐색하여 최솟값을 구하는 문제이다.  트리 순회에 대한 개념이 부족한 상태로 크루스칼을 써서 돌려야하는지 DFS로 모든 노드를 시작으로 다 돌려봐야하는지 고민을 많이 하다가 결국 해설을 참고했다.

 

문제를 천천히 곱씹어보자.

 

sales 배열의 크기(이하 size)는 2 이상 300,000이다. 이 회사의 구성원은 최대 2명부터 30만명으로 되어있다.

 

노드 1은 항상 CEO이어서 팀원이 아닌 팀장에만 속한다. 한마디로 루트노드이다.

팀은 팀장 1명과 팀원 n (1 ≤ a ≤ sales-1)으로 이루어져있다.

 

구상

1) 워크숍에서 참석하는 경우의 수를 무식하게 다 구해보면 총 4가지이다. (감이 안잡힐 때는 일단 천천히 뜯어보는게 최고다)

   1. 팀장 o - 팀원 o

   2. 팀장 x - 팀원 o 

   3. 팀장 o - 팀원 x

   4. 팀장 x - 팀원 x

 

4가지의 경우 중 문제가 되는 부분은 4번. 팀장 x- 팀원 x이다. 팀에서 최소 1명은 워크숍에 참석해야하기 때문에 이 부분은 예외처리가 필요해 보인다. 

 

2) 4번. 팀장 x- 팀원 x

만약 한 팀에서 굳이 한 명을 워크숍에 참석해야하는 경우라면 팀에서 최소의 매출을 찍는 팀원을 보내는 것이 팀에 제일 효율적이다.

 

3) 이러한 과정을 동적 계획법을 사용하여 참석한 경우와 안한 경우의 값을 저장해준다. 

cost[1][0] : 1번이 참석하지 않을 경우 cost

cost[1][1]  : 1번이 참석할 경우 cost

 

시뮬레이션

아래의 트리로 시뮬레이션을 한 번 돌려보자.

 

 

☛ 노드 1 순회 시작

----cost[1][0] = 0

----cost[1][1] = 5

----A싸이클 (부모 1)>  자식 : 2, 4 탐색 

--------------------cost[2][0] = 0

--------------------cost[2][1] = 6

--------------------B싸이클(부모 2) >  자식 : 5, 3 탐색 

-------------------------------------cost[5][0] = 0

-------------------------------------cost[5][1] = 4

-------------------------------------cost[3][0] = 0

-------------------------------------cost[3][1] = 5

--------------------B싸이클 종료

--------------------cost[4][0] = 0

--------------------cost[4][1] = 3

----A싸이클 종료

 

 

트리를 순회하여 각 노드가 참석할 경우, 안할 경우의 cost를 저장해준다.

 

여기서 부모 노드를 하나의 싸이클의 기점(A, B)으로 보자  이 하나의 싸이클을 하나의 팀이라고 보면 된다.

 

이 싸이클 안에서 해야할 과제는 이 4가지의 경우를 모두 조사해서 값을 매긴 다음 cost[부모][]에 Bottom-up방식으로 저장해주면된다. 적은 비용을 구하는 것이 목적이므로 (팀원이 참석할 경우 , 참석 안할 경우) 중 최소의 값을 선택해서 팀장에게 전해주면 된다.

 

1) cost[자식][0] < cost[자식][1]  ▸ 팀원x : 해당 팀원(child)이 참여 안하는게 더 적은 비용이 드는 경우 

1. 팀장 o - 팀원 x  : cost[부모][1] += cost[자식][0]
2. 팀장 x - 팀원 x : cost[부모][0] += cost[자식][0]
3. 이 로직 안에서 해야할 것이 있다. 2번 팀장x-팀원x 이므로 이 경우를 대비해 팀원의 최소 매출 비용을 구해야한다.
   1. extra_cost = Math.min(extra_cost, cost[자식][1] - cost[자식][0]); 

* cost[자식][0]를 빼는 이유는 cost[부모][0] += cost[자식][0]에서 먼저 더해줬기 때문

 

2) cost[자식][0] >= cost[자식][1]  ▸ 팀원 o 해당 팀원(child)이 참여하는게 더 적은 비용이 드는 경우  

1. 팀장 o - 팀원 o : cost[부모][1] += cost[자식][1]
2. 팀장 x - 팀원 o : cost[부모][0] += cost[자식][1]

 

 

 

이제 그 싸이클을 자세히 뜯어보자. Bottom-up이기 때문에 제일 하위 문제인 B싸이클부터 탐색해보자.

B 싸이클 (부모 노드 2)

☛ 자식 3 탐색 

1) cost[3][0] = 0 < cost[3][1] =5

1. 팀장 o - 팀원 x  : cost[2][1] += cost[3][0]  => 6 + 0 = 6
2. 팀장 x - 팀원 x : cost[2][0] += cost[3][0] => 0 +0 = 0
3. extra_cost = 5-0 =5

 

☛ 자식 5 탐색 

1) cost[5][0] = 0 < cost[5][1] =4

1. 팀장 o - 팀원 x  : cost[2][1] += cost[5][0]  => 6 + 0 = 6
2. 팀장 x - 팀원 x : cost[2][0] += cost[5][0] => 0 +0 = 0
3. extra_cost = 4 < 5 = 4

 

B 싸이클 종료 

싸이클 종료와 함께 extra_cost값을 저장해준다.

> extra_cost =4 이므로, 아무도 참석 안할 경우 자식 5가 참석을 해야 최소의 매출 하락을 낼 수 있다.

cost[2][0] += extra_cost => 0+4 = 4

cost[2][1] = 6

 

B 싸이클 종료 시점

 

이제 거슬러서 A싸이클을 탐색해보자.

A 싸이클 (부모 노드 1)

☛ 자식 2 탐색 

1) cost[2][0] = 4 < cost[2][1] =6 

1. 팀장 o - 팀원 x  : cost[1][1] += cost[2][0]  => 5 + 4 = 9
2. 팀장 x - 팀원 x : cost[1][0] += cost[2][0] => 0 +4 = 4
3. extra_cost = cost[2][1] - cost[2][0] = 2

 

☛ 자식 4 탐색 

1) cost[4][0] = 0 < cost[4][1] = 3

1. 팀장 o - 팀원 x  : cost[1][1] += cost[4][0]  => 9 + 0 = 9
2. 팀장 x - 팀원 x : cost[1][0] += cost[4][0] => 4 +0 = 4
3. extra_cost = 2 < 3 =  2

 

A 싸이클 종료

> extra_cost =4 이므로, 아무도 참석 안할 경우 자식 2가 참석을 해야 최소의 매출 하락을 낼 수 있다.

cost[1][0] += extra_cost => 4+2 = 6

cost[1][1] = 9

 

A 싸이클 종료

 

모든 싸이클을 돌렸으니 이제 CEO가 참석할 경우 vs CEO가 참석하지 않을 경우 중 작은 값을 구해서 최소 매출 하락을 고르면 된다. 

cost[1][0] = 6 < cost[1][1] = 9

 

따라서, 답은 6이다.

 

풀이 코드 

그림이 잘 안그려질 경우에는 일단 작은 케이스를 만들어서 무식하게 모든 과정을 답사한 다음에 한 싸이클의 그림을 이해하는 방식으로 다가가야겠다. 

// blind #7 매출하락최소화 - 트리 순회, DP  
import java.util.*;

public class MinimizeSalesDecline {
	
	static int[][] cost;
	static int[] extra;
	static List<Integer>[] sales_info;
	static int[] g_sales;
	static int INF = Integer.MAX_VALUE;
	
	public static int solution(int[] sales, int[][] links) {
        int answer = INF;
        
        // ====== 초기 설정======= 
        int n1 = sales.length;
        int n2 = links.length;
        cost = new int[n1+1][2];
        extra = new int[n1+1];
        sales_info = new ArrayList[n1+1];
        g_sales = new int[n1];


        for(int i=0; i<n1; i++	) {
        	g_sales[i] = sales[i];
        }
        
        for(int i=0; i<n1+1; i++) {
        	sales_info[i] = new ArrayList<>();
        }
        
        for(int i=0; i<n2; i++) {
        	sales_info[links[i][0]].add(links[i][1]);
        }
        
        // ========================= 
        //CEO 1을 기준으로 모든 노드 순회 
        trevarsal(1); 
        
        // 1번 팀장이 참여한 경우 vs 참여하지않은 경우 
        return Math.min(cost[1][0], cost[1][1]);
    }
	
	// 노드 순회 (후위)  
	static void trevarsal(int pos) {
		int child_num = sales_info[pos].size();
		
		cost[pos][0] = 0; // 참석 x 
		cost[pos][1] = g_sales[pos-1]; // 참석 o 
		
		// leaf 노드 도착하면 값만 넣고 return (only 팀원 not 팀장)
		if(child_num ==0 )return;
		
		int extra_cost = INF;
		// ============== 싸이클 시작 ================
		// 부모 -> 자식 탐색 
		for(int child : sales_info[pos]) {
			trevarsal(child); // child 탐색 
			
			// ex) parent1 -> (4,2)	탐색 후 아래 로직 실행 
				
			// 팀원x : 해당 팀원(child)이 참여 안하는게 더 적은 비용이 드는 경우 
			if(cost[child][0] < cost[child][1]) {
				cost[pos][0] += cost[child][0]; // 팀장 x 팀원 x -> 예외처리 필요(다른 자식노드 참여) 
				cost[pos][1] += cost[child][0]; // 팀장 o 팀원 x 
					
				// 팀장x 팀원x인 경우 한 팀에 최소 한명이니깐 팀원 중 최소비용 추가해놓기 
				extra_cost = Math.min(extra_cost, cost[child][1] - cost[child][0]);
			}
			// 팀원 o : 해당 팀원(child)이 참여하는게 더 적은 비용이 드는 경우  
			else {
				cost[pos][0] += cost[child][1]; // 팀장 x 팀원 o
				cost[pos][1] += cost[child][1]; // 팀장 o 팀원 o
					
				// 팀장x 팀원o 이면 다른 자식이 참여헀으니깐 0으로 초기화 
				extra_cost = 0;
			}
		}
		// ============== 싸이클 종료 ================
        
//		System.out.println(pos +" 팀장 참여안할 때 최소비용드는 팀원 cost: " + extra_cost);
		cost[pos][0] += extra_cost; // 아무도 참석 안할 경우 최소비용 팀원 추가
		
	
	}
	
    
    // 메인 함수
	public static void main(String[] args) {
//		int[] sales = {14, 17, 15, 18, 19, 14, 13, 16, 28, 17};
//		int[][] links = { {10, 8}, {1, 9}, {9, 7}, 
//						{5, 4}, {1, 5}, {5, 10}, {10, 6},
//						{1, 3}, {10, 2} };
		
		int[] sales = {5,6,5,3,4};
		int[][] links = { {2,3}, {1,4}, {2,5}, {1,2} };
		
		System.out.println(solution(sales, links));
	}

}