[프로그래머스/Level3] 다단계 칫솔 판매 (JAVA)

📖 문제

프로그래머스

 

 

💡  풀이 방식

• 재귀함수

 

필요 자료구조
- 사람 객체 (현재 사람, 부모 객체, 수익) + 객체 내 수익 계산하는 재귀함수
- 자기 자신을 key로, 부모 객체를 value로 갖는 Map

 

 

1. 자기 자신을 key로, 부모 객체를 value로 갖는 Map을 만든다.

2. 해당 map에 각 판매원의 이름과 부모 객체의 정보(현재 사람, null, 0)를 저장한다.

3. 각 판매원을 조직에 참여시킨 사람 이름 배열(referral)을 돌며 부모를 등록한다. 

4. 판매 집계 데이터를 돌며 수익을 계산한다.

5. 계산한 수익을 정답 배열에 저장해 출력한다.

 

 

🔺 코드

import java.util.*;
 
class Solution {    
    public int[] solution(String[] enroll, String[] referral, String[] seller, int[] amount) {
        
        Map<String, Person> map = new HashMap<>();  // key: 자기 자신, value: 부모
        for(String x : enroll) {
            map.put(x, new Person(x, null, 0));
        }
        
        // 부모 등록하기
        for(int i = 0 ; i < enroll.length ; i++) {
            if(referral[i].equals("-")) { 
                continue;
            }
            
            map.get(enroll[i]).prev = map.get(referral[i]);
        }
        
        // 수익 계산하기
        for(int i = 0 ; i < seller.length ; i++) {
            map.get(seller[i]).calc(amount[i] * 100);
        }
        
        // 정답 출력하기
        int[] answer = new int[enroll.length];
        for(int i = 0 ; i < answer.length ; i++) {
            answer[i] = map.get(enroll[i]).val;
        }        
        return answer;
    }
}
 
class Person {
    String now;
    Person prev;    // 사람 객체 !!
    int val;
    
    public Person(String now, Person prev, int val) {
        this.now = now;
        this.prev = prev;
        this.val = val;
    }
    
    // 재귀함수
    public void calc(int val) {
        int profitToParent = val/10;
        this.val += (val - profitToParent);
        
        if(this.prev != null && profitToParent >= 1) {
            this.prev.calc(profitToParent);
        }
    }
}

 

 

 

➕ 다른 풀이 방식

- (멤버, 추천인)을 저장하는 Map과 (멤버, 수익)을 저장하는 Map 2개를 만들어 활용하셨다. 개인적으로는 이게 더 이해가 잘 되는 풀이인 듯

velog

 

 

---

💦 어려웠던 점

- 트리 자료구조 문제라고 생각해서 양방향으로 이전 부모 값, 아래 자식 값을 모두 저장해서 활용해야 하나.. 라는 생각을 했다.

- 어떤 자료구조를 써야할지 고민을 꽤 오래 한 것 같다.

 

 

🧐 새로 알게 된 내용

- 새로 생성한 객체의 인자로 본인 자료형을 쓸 수 있는 것

-                         "               내 메소드를 생성하고 활용하는 것

 

 

 

1회독	2회독	3회독	4회독	5회독
V

---

(참고)

프로그래머스 - 다단계 칫솔 판매 문제 (자바)