[Java] 트리, 구현 | 프로그래머스 다단계 칫솔 판매

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

 

문제 개요
다단계 판매 조직에서 각 판매원의 이익을 계산하는 알고리즘을 구현하는 것이 목표였다.

주요 규칙은 아래와 같다.

• 판매원이 발생시킨 이익의 10%를 추천인에게 분배(1원 미만은 분배하지 않음)
• 나머지는 자신이 가짐
• 이 과정이 재귀적으로 상위 추천인에게도 적용됨

처음 시도한 방법

class Node {
    String name;
    Node parent;
    int income;
   
}

• 처음에는 트리 구조를 구현하기 위해 Node 클래스를 만들어 문제해결을 시도해보았다.
• 각 판매원을 노드로 생성하고 포인터로 연결하는 구조를 생각했지만
• 판매원 검색과 수익 갱신 과정에 있어서 성능이 좋지 않다는 것을 알게 되었다.

 

접근 방법

• 자료구조 선택
  • HashMap을 활용하여 두 가지 매핑 관계를 저장
    • worker : 판매원 -> 추천인 관계  // Map<String, String> worker = new HashMap<>();
    • 판매원들의 관계를 해시맵 worker로  표현
    • income: 판매원 -> 수익금 관계  // Map<String, Integer> income = new HashMap<>();
    • 판매원 이름을 키로, 누적 이익을 값으로 하는 해시맵 income을 사용

for(int i=0; i < enroll.length; i++){
    worker.put(enroll[i], referral[i]);
    income.put(enroll[i], 0);
}

• 이익 분배 로직
  • 총 이익 = 각 판매 건수 * 100
  • 상위 추천인으로 올라가면서 10% 분배, 나머지는 자신이 가짐
  • 분배 금액이 0이 될 때까지 반복
  • 반복 종료 조건 : 추천인 없는 경우 ("-"), 분배할 이익이 없을 경우 (currentIncome > 0)

for(int i=0; i < seller.length; i++){
    String currentSeller = seller[i];
    int currentIncome = amount[i] * 100;

    while(!currentSeller.equals("-") && currentIncome > 0){
        int shareIncome = currentIncome/10;
        int earn = currentIncome - shareIncome;
        income.put(currentSeller, income.get(currentSeller)+earn);

        currentSeller = worker.get(currentSeller);
        currentIncome = shareIncome;
    }
}

 

 

배운 점 

처음 접근할 seller에 대한 노드 클래스를 만들어 포인터로 트리구조를 구현했지만 성능이 좋지 않았다.

트리 구조(ex : 다단계) => 해당 문제의 경우 단순 상향 탐색만 필요했기 때문에 HashMap으로 구현이 충분했다. 해당 문제에 실제로 필요한 구현만 하면 되었기 때문에 다른 문제를 풀 때도 Node 클래스의 구현이 해당 문제를 푸는데 있어서 정말 최선인지 다시 생각해봐야겠다.

또한 빈번한 조회가 필요한 상황, 데이터 간 관계를 표현해야 하는 경우일 때 HashMap 활용을 우선적으로 고려해보아야겠다.