[Swift - 프로그래머스] 다단계 칫솔 판매

🕵🏻  문제 해석 

---

민호는 다단계 조직으로 칫솔을 판매하는 사업을 하고 있습니다. 이 피라미드 식의 조직은 판매원이 칫솔을 판매하였을 때, 그 수익금의 10%를 자신을 소개해준 판매원에게 분배합니다. 분배받은 판매원도 누군가의 소개를 받았었다면 분배받은 금액의 10%와 자신의 수익금 10%을 마찬가지로 분배합니다. 이런 식으로 모든 판매원의 수익금을 정산하였을 때, 그 금액을 리턴하는 문제입니다. 

문제에서 제공하는 예시를 봅시다!

판매원	판매 수량	수익금
young	12	1,200원
john	4	400원
tod	2	200원
emily	5	500원
mary	10	1,000원

 

문제에서 주어진 수익금과 소개 구조를 바탕으로 조직도를 그려봤습니다. 파란색으로 칠해진 사각형들은 칫솔을 판매하여 수익금이 발생한 판매원들을 표시한 것입니다. 판매원에게 소개 시켜준 사람은 한 명이므로 트리구조라고 볼 수 있겠죠? 

따라서 파란색으로 칠한 판매원들로 부터 발생하는 분배금을 센터에 도달할 때까지 계속 10%로 계산하여 전달하면 문제를 해결할 수 있겠습니다. 

🤔 풀이 과정

---

이제 트리구조인 것을 알겠고 따로 node class를 만들어서 접근해보려했으나 딕셔너리를 사용하는 것이 더 간편한 것 같아서 판매원과 추천인을 매칭시켜줄 connections 딕셔너리와, 판매원과 수익금을 저장할 profits 딕셔너리, 이 두 가지를 만들었습니다.

제가 문제를 풀면서 가장 헷갈렸던 부분은 "수익이 발생한 단 하나의 노드로부터 부모 노드를 따라 계산한 분배금만을 전달한다"라는 부분이었습니다. 예를 들어, 위의 트리 구조를 보면 Mary처럼 자식 노드가 여러 개인 경우 전달받은 분배금 또한 여러 개가 됩니다.

이때, (분배받은 금액들의 합 + 자신의 수익금)의 10%를  센터에 전달하는 것이 아닌, [young, emily, tod]들로부터 분배된 금액마다 따로 10%씩 처리하여 전달해야 한다는 것이 무척이나 헷갈렸습니다.

그럼 위의 내용을 바탕으로 트리 탐색의 시작점은 판매 수익이 발생한 [young, john, tod, emily, mary]가 될 것이고 각각의 탐색 순서는 다음과 같습니다.

• young - edward - mary - center
• john - center
• tod - jaymie - mary - center
• emily - mary - center
• mary - center

따라서, 수익이 발생한 노드들에서 center에 도달할 때까지 분배금을 전달할 재귀 함수를 각각 호출하여 문제를 해결해보았습니다. 

이때, 재귀 함수에서 전달할 분배금이 0이 되면 전달하는 의미가 더 이상 없으므로 리턴 처리를 해주어 시간을 좀 더 단축할 수 있습니다.

📦  문제 풀이 & 코드

---

import Foundation

func solution(_ enroll:[String], _ referral:[String], _ seller:[String], _ amount:[Int]) -> [Int] {
    // [판매원 : 추천인] , [판매원 : 수익금]
    var connections = Dictionary<String, String>()
    var profits = Dictionary<String, Int>()
    profits["-"] = 0
    
    // 분배금 계산, Int 생성자로 절사 처리
    func calculate(_ profit: Int) -> Int {
        return Int(Double(profit) * 0.1)
    }

    // 분배금 전달 함수
    func pass(_ name: String, earn: Int) {
        // 분배금이 0에 수렴하면 더 이상 전달하는 의미가 없으므로, return
        if earn == 0 {
            return
        }
        
        // 분배금 전달
        profits[name]! += earn
        if name != "-" {
            // 자신을 추천한 추천인이 존재하면 10%를 제한 금액은 가지고 분배금을 넘긴다.
            profits[name]! -= calculate(earn)
            pass(connections[name]!, earn: calculate(earn))
        }
    }
    
    // 딕셔너리 초기화
    for i in 0..<enroll.count {
        connections[enroll[i]] = referral[i]
        profits[enroll[i]] = 0
    }
    
    // 수익금이 발생한 노드들로 부터 분배금을 먼저 계산하고 자신의 판매 수익을 더해 준다.
    for i in 0..<seller.count {
        pass(connections[seller[i]]!, earn: calculate(amount[i] * 100))
        // 이미 분배를 해준 상황이므로 100 * 0.9 = 90
        profits[seller[i]]! += amount[i] * 90
    }
   
    // enroll 입력 순서대로 수익금을 매핑
    return enroll.map{profits[$0]!}
}

• 문제링크 : https://programmers.co.kr/learn/courses/30/lessons/77486

코딩테스트 연습 - 다단계 칫솔 판매