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

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

프로그래머스

 

2023.07.29 기준 Level 3

 

알고리즘 공부를 위해 풀고 기록하는 글입니다!
참고만 해주시고 더 좋은 풀이법이 있다면 알려주세요!

 

아이디어

다단계 조직은 트리 구조를 이루고 있습니다.

각 판매원(노드)는 자신을 초대한 사람을 부모 노드로 가집니다.

따라서 sam은 edward를 부모 노드로 가지고 edward는 mary를 부모 노드로 가집니다. 마지막으로 mary는 center(민호)를 부모 노드로 가집니다.

 

우리는 이 트리를 가지고 판매원이 판매를 하면 10퍼센트씩 부모 노드로 전달하면 됩니다.

 

딕셔너리를 활용하여 이 트리를 저장하는 방식을 떠올렸습니다.

Key에는 판매원의 이름, Value에는 판매원을 참여시킨 추천인의 이름이 들어가게 됩니다.

 

그리고 각 판매원의 이익금도 저장해야 하기 때문에 마찬가지로 딕셔너리를 사용했습니다.

Key에는 판매원 이름, Value에는 이익금을 저장합니다.

 

이제 각 판매원의 이익을 분배하는 작업을 하면 됩니다.

판매를 한 판매원 노드부터 시작해서 재귀적으로 트리를 탐색하며 이익금을 분배합니다.

 

sam이 판매를 했다면 판매금의 10퍼센트를 부모 노드인 edward에 지급합니다. 부모 노드는 앞서 트리를 저장한 딕셔너리에서 찾아오면 됩니다. 

edward는 받은 분배금을 mary에게 다시 10퍼센트 나누어 분배합니다.

mary는 center에게 10퍼센트를 분배합니다.

 

1. 부모 노드를 찾는다.
2. 부모 노드에게 줄 10퍼센트를 제외한 이익금을 본인이 가진다.
3. 부모 노드에게 10퍼센트를 분배한다.
4. 1~3번 과정을 반복한다.

이 과정은 재귀적인 성향을 가지기 때문에 재귀 함수로 구현하면 됩니다.

 

풀이

fileprivate func solution(_ enroll:[String], _ referral:[String], _ seller:[String], _ amount:[Int]) -> [Int] {
    var resultDict = [String: Int]()    // key: 판매원 이름, value: 이익금
    var tree = [String: String]() // Key: 판매원 이름, value: 판매원을 참여시킨 추천인 이름
    
    for i in 0..<enroll.count {
        let person = enroll[i]
        resultDict[person] = 0
        tree[person] = referral[i]
    }
    
    // 이익을 분배하는 함수 (추천인들에게도 10퍼센트씩 분배)
    func distributeProfits(name: String, profits: Int) {
        if profits < 1 {
            return
        }
        
        // 이익 계산
        let profitsForParent = profits / 10
        let currentSellerProfit = profits - profitsForParent
        
        resultDict[name, default: 0] += currentSellerProfit
        
        let parent = tree[name]! // parent는 추천인을 의미

        if parent != "-" {
            distributeProfits(name: parent, profits: profitsForParent)
        }
    }
    
    for i in 0..<seller.count {
        let sellerName = seller[i]
        let profits = amount[i] * 100
        
        distributeProfits(name: sellerName, profits: profits)
    }
    
    var result = [Int]()
    
    for name in enroll {
        let profits = resultDict[name]!
        result.append(profits)
    }
    
    return result
}

우선 이익금과 tree를 저장할 2개의 딕셔너리를 만들었습니다.

딕셔너리를 사용하면 O(1)의 시간 복잡도로 데이터에 접근할 수 있기 때문에 효율적입니다.

 

enrrol과  referral 배열을 순회하며 딕셔너리에 기본 데이터들을 채웁니다.

 

이익을 분배하는 재귀 함수인 distributeProfits를 구현했습니다.

1원 미만은 분배하지 않는다고 문제 조건에서 제시했기 때문에 재귀 종료 조건으로 profits < 1을 넣었습니다.

 

parent가 "-"인 경우는 center(민호)가 부모 노드인 경우이고 이 경우는 결과 값에 포함하지 않기 때문에 더이상 재귀함수를 호출하지 않도록 했습니다.

 

다음으로 seller 배열을 순회하며 이익금을 배분했습니다.

 

이 과정을 마치면 resultDict에는 각 판매원이 얻은 이익금이 잘 들어가있게 됩니다.

 

리턴 타입 형식에 맞춰 enroll의 순서대로 resultDict에서 이익금을 빼서 어레이에 저장하고 리턴했습니다.

 

마무리

문제는 매우 길고 거창했지만 결국 트리를 탐색하는 문제였습니다.

보통 부모로부터 자식 노드를 탐색하는데 이 문제는 반대로 자식 노드부터 시작해서 부모 노드를 찾아가는 과정이 필요했습니다.

트리를 탐색할 때에는 재귀가 효과적입니다.

트리를 저장하기 위해 딕셔너리를 사용한 것도 주요했습니다!