[프로그래머스/자바] 다단계 칫솔 판매 풀이

https://school.programmers.co.kr/learn/courses/30/lessons/77486

프로그래머스

 

 

seller/amount의 최대 길이는 100,000이기 때문에

판매한 금액마다 부모의 끝까지 올라간다면 시간 측면에서 비효율적이라고 생각했다. 

그래서 판매한 금액들을 ArrayList에 저장하고,

리프 노드의 금액 */ 10을 자신의 한 단계 부모에게만 전달하는 방식으로 구현해봤다.

 

그리고 리프 노드에서 처리가 끝나면 그 노드와 부모의 연결을 끊어주면,

또 다른 리프노드가 생겨나고, 모든 노드가 리프 노드가 되어 처리할 때까지 반복한다.

 

 

 

 

이를 구현하기 위해서 위상 정렬을 활용했다.

        for(int i=0;i<n;i++) {
            if(!referral[i].equals("-"))
                outdegree[index_map.get(referral[i])]++;
            parent[i] = referral[i];
        }
        
        Queue<String> q = new LinkedList<>();
        for(int i=0;i<n;i++)
            if(outdegree[i] == 0)
                q.offer(enroll[i]);

위상 정렬에는 루트 노드를 시작으로 큐에 삽입하기 때문에 indegree를 사용했지만,

여기서는 리프 노드를 시작으로 하기 때문에 outdegree를 count한다.

outdegree가 0인 노드가 리프 노드이므로 큐에 삽입한다.

 

 

 

 

        while(!q.isEmpty()) {
            String now = q.poll();
            
            int i = index_map.get(now);
            String p = parent[index_map.get(now)];
            boolean flag = p.equals("-") ? false : true;
            if(flag && --outdegree[index_map.get(p)] == 0)
                q.offer(p);
            
            ArrayList<Integer> now_profit_list = profit_map.get(now);
            ArrayList<Integer> parent_profit_list = new ArrayList<>();
            if(flag)
                parent_profit_list = profit_map.get(p);
            
            for(int profit : now_profit_list) {
                int parent_profit = profit / 10;
                answer[i] += profit - parent_profit;
                if(flag && parent_profit != 0)
                    parent_profit_list.add(parent_profit);
            }
        }

그리고 큐에 삽입한 노드의 부모와 연결을 끊어주기 위해 부모의 outdegree를 1 감소시키고,

감소시킨 부모의 outdegree가 0이 되었다면 리프 노드이므로 큐에 삽입한다.

이 과정을 큐가 빌 때까지 처리해주면 된다.

 

큐에서 하나씩 꺼낼때마다 자신의 answer에는 자신의 이익 * 0.9를 더해주고,

부모의 profit list에는 자신의 이익 * 0.1을 더해준다.

이렇게 하면 seller의 크기가 아닌 판매원의 인원만큼만 처리해주면 모든 answer를 구할 수 있다.

만약 큐에서 꺼낸 원소가 root라면, (부모가 "-") 자신의 answer에만 더해준다.

 

 

 

 

 

 

다 풀고 나니, 금액의 범위가 크지 않아 그렇게 깊이 올라가지 않을 것같고

내가 푼 방식은 ArrayList로 이익을 관리하기 때문에 값을 꺼낼 때의 시간도 있을 것 같다.

seller/amount의 원소마다 자신의 금액, 부모의 금액까지 계산해준다면 재귀적으로 간단하게 코드를 짤 수 있을 듯.

그래도 시간적으로 굉장히 여유있게 통과한 것 같아 뿌듯!

 

 

 

 

 

 

전체 코드

import java.util.*;

class Solution {
    HashMap<String, Integer> index_map = new HashMap<>();
    HashMap<String, ArrayList<Integer>> profit_map = new HashMap<>();
    String[] parent;
    int[] outdegree;
    int[] answer;
    int n;
    
    public int[] solution(String[] enroll, String[] referral, String[] seller, int[] amount) {
        n = enroll.length;
        parent = new String[n];
        outdegree = new int[n];
        answer = new int[n];
        
        for(int i=0;i<n;i++) {
            index_map.put(enroll[i], i);
            profit_map.put(enroll[i], new ArrayList<>());
        }
        
        for(int i=0;i<n;i++) {
            if(!referral[i].equals("-"))
                outdegree[index_map.get(referral[i])]++;
            parent[i] = referral[i];
        }
        
        int m = seller.length;
        for(int i=0;i<m;i++) 
            profit_map.get(seller[i]).add(amount[i] * 100);
        
        Queue<String> q = new LinkedList<>();
        for(int i=0;i<n;i++)
            if(outdegree[i] == 0)
                q.offer(enroll[i]);
        
        while(!q.isEmpty()) {
            String now = q.poll();
            
            int i = index_map.get(now);
            String p = parent[index_map.get(now)];
            boolean flag = p.equals("-") ? false : true;
            if(flag && --outdegree[index_map.get(p)] == 0)
                q.offer(p);
            
            ArrayList<Integer> now_profit_list = profit_map.get(now);
            ArrayList<Integer> parent_profit_list = new ArrayList<>();
            if(flag)
                parent_profit_list = profit_map.get(p);
            
            for(int profit : now_profit_list) {
                int parent_profit = profit / 10;
                answer[i] += profit - parent_profit;
                if(flag && parent_profit != 0)
                    parent_profit_list.add(parent_profit);
            }
        }
        
        return answer;
    }
}