프로그래머스 - 다단계 칫솔 판매(Lv.3)

문제 링크

풀이

import Foundation

func solution(_ enroll:[String], _ referral:[String], _ seller:[String], _ amount:[Int]) -> [Int] {
    var dic: [String: Node] = [:]
    enroll.forEach {
        dic[$0] = Node()
    }
    
    // 부모 맵핑
    for (index, name) in referral.enumerated() where name != "-" {
        let child = enroll[index]
        dic[child]!.parent = name   // 부모 매핑
    }
    
    // 판매금액 추가
    for (index, sellerName) in seller.enumerated() {
        var amount = amount[index] * 100
        var tax = amount / 10   // 징수금액
        dic[sellerName]!.amount += amount - tax
        
        // 징수금액 부모에게 배분
        var name = sellerName
        while let parent = dic[name]!.parent {
            amount = tax
            tax = tax / 10
            dic[parent]!.amount += amount - tax
            
            name = parent
            if tax == 0 {   // 더이상 배분할 금액이 없다면 탈출
                break
            }
        }
    }
    
    var result: [Int] = []
    
    for name in enroll {
        result.append(dic[name]!.amount)
    }
    
    return result
}

// 판매자
struct Node {
    var parent: String? = nil
    var amount: Int = 0
}

후기

굉장히 지문이 불친절했던 문제.
직접 풀어봤던 분들은 모두 한번씩 삽질을 경험해봤을 듯 하다.
복잡하게 들어가면 오히려 낭패를 본다.
그래프 구조로 노드를 구성한 후 부모마다 세금징수하게하면 된다.
DFS니 후순위 정렬이니 그런거 생각하지말고 간단히 가는게 답인 문제.