Today I Learned

주말에 있는 프로그래머스 코테를 대비해 열심히 문제를 풀고 있다. 오늘은 구현 문제를 풀었다.

다단계 칫솔 판매

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

문제

다단계 회사에서 칫솔을 팔면 판매 수익금의 10%가 추천인에게 간다. 칫솔은 개당 100원의 수익이 남고, 10%에서 원단위 미만은 절사된다. 각 판매원의 이름을 담은 배열 enroll, 각 판매원의 추천인 이름을 담은 배열 referral, 칫솔 판매원 이름을 나열한 배열 seller, 칫솔 판매 수량을 seller에 맞춰 나열한 배열 amount가 주어질 때, 각 판매원의 이득 금액을 배열에 담아 반환하라.

구현 과정

1. 우선 노드 클래스를 만들어 이름, 수익금, 부모노드의 정보를 담는다. 생성자는 일단 이름만 넣고 나머지 필드는 직접 입력한다.

2. 2차원 리스트를 만들어 graph를 구현할까 생각해봤지만, 문제의 조건에서 추천한 사람은 추천 받아서 들어온 사람보다 항상 enroll에서 먼저 등장한다는 점 때문에 일반적인 일차원 리스트와 node의 parent로 충분해 보였다.

3. 노드를 담을 리스트와 각 이름이 enroll에서 몇번째 인덱스인지 저장하는 map을 생성한다. map이 필요한 이유는 인덱스를 nodeList에서도 그대로 가져가고, referral 정보를 활용할 때 필요하기 때문이다. 메서드를 만드는 것보다 map에 저장하는 것이 시간복잡도 측면에서 빠르기 때문에 선택했다.

4. 노드를 생성해 이름과 부모 노드에 대한 정보를 넣고 노드 리스트에 넣는다.

5. 판매금액을 계산하면서 부모 노드에게 바로바로 정산한다. 10%를 계산한뒤 내가 그 금액을 차감한 만큼 갖고, 부모노드에게 10%를 수익으로 건내는 방식으로 메서드를 만든다. 해당 메서드를 부모가 없거나 정산금이 0이될때까지 타고 올라가도록 재귀형식으로 만들어 정산한다.

6. nodeList를 순회하면서 각자의 금액을 배열에 담아 반환하면 끝.

Trouble

• 판매 정보 등록 후 한꺼번에 정산으로 처음에 시도했었는데 테스트케이스는 통과했지만 코드 실행시 2개 빼고 전부 실패했다. 원단위 절삭 때문에 오차가 발생하기 때문이었다.

• 그래서 매 판매 순간마다 정산하는 방식으로 변경하니 통과할 수 있었다.

Java 코드

import java.util.*;
class Node {
    String name;
    Node parent;
    int money = 0;
    
    Node(String name) {
        this.name = name;
    }
}

class Solution {
    // 정산
    public void pay(Node node, int rev){    
        int payment = rev / 10;
        
        node.money += rev - payment;
        if(node.parent == null || payment == 0) return;
        pay(node.parent, payment);
    }
    
    public int[] solution(String[] enroll, String[] referral, String[] seller, int[] amount) {
        int n = enroll.length;
        int m = seller.length;
        
        List<Node> nodeList = new ArrayList<>();
        Map<String, Integer> nameOrder = new HashMap<>();
        
        // nodeList에 노드 생성해서 삽입
        for(int i=0; i<n; i++){
            Node node = new Node(enroll[i]);
            nameOrder.put(enroll[i], i);
            
            if(!referral[i].equals("-")){
                int p = nameOrder.get(referral[i]);
                Node parent = nodeList.get(p);
                node.parent = parent;
            }
            
            nodeList.add(node);
        }
        
        // 판매 금액 넣기
        for(int i=0; i<m; i++){
            int index = nameOrder.get(seller[i]);
            Node node = nodeList.get(index);
            int revenue = amount[i] * 100;           
            pay(node, revenue);
        
        }
        
        int[] answer = new int[n];
        
        // 출력값반환
        for(int i=0; i<n; i++){
            Node node = nodeList.get(i);
            answer[i] = node.money;
        }
        
        
        
        return answer;
    }
}