본문 바로가기

Dot Algo∙ DS/PS

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

    #7 매출 하락 최소화

    2021 카카오 블라인드

    난이도 : LEVEL 4

    유형 : 트리 순회 / DP 

     

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

    CEO를 포함하여 모든 직원은 팀장 또는 팀원이라는 직위를 가지고 있으며 그림에서는 팀장과 팀원의 관계를 화살표로 표시하고 있습니다. 화살표가 시작되는 쪽의 직원은 팀장, 화살표를 받는

    programmers.co.kr

    [문제]

    직원들의 하루평균 매출액 값을 담은 배열 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));
    	}
    
    }