문제 링크

문제 풀이 아이디어

구현

문제를 풀기 위해서 특별한 알고리즘은 필요가 없는 구현 문제입니다.

Dictionary 활용

문제 전반에 걸쳐서 사람을 구분하기 위해서 index와 이름 (String)을 혼용해서 사용하고 있습니다. 그리고 마지막에 답을 출력할 때는 index에 맞추어서 수익을 출력해야 합니다. 따라서 헷갈리지 않도록 dictionary를 활용해서 O(1)로 이름에 맞는 index를 찾을 수 있도록 합니다.

🚫 주의할 점

seller에는 같은 이름이 중복되어 들어있을 수 있다고 합니다. 즉 어떤 사람이 얼마나 팔았느냐가 정리되어 있는게 아니라 판매가 한 건당 얼마를 팔았는지 들어있는 raw data라고 볼 수 있습니다.

따라서 좀 더 반복문의 횟수를 줄이기 위해서 모든 판매를 사람별로 정리해서 즉 판매를 다 합쳐서 하나의 Array에 정돈하고 풀고 싶은 마음이 들 수도 있습니다.

하지만 수익을 분배할 때 원단위 이하는 절삭한다는 조건이 있습니다. 판매금액을 다 합쳐버린 경우에는 원래는 원단위 절삭이 일어나야 하는 계산이 일어나지 않을 수 있습니다. 예를 들어 9원과 1원의 판매금액은 둘 다 원단위 절삭이 되어 추천인에게 가는 금액이 0원인데 둘을 합쳐서 10원이 되면 추천인에게 가는 금액이 1원이 생깁니다.

문제의 예시를 보면 전체 판매액을 기준으로 분배하는 것이 아니라 건당 판매액을 기준으로 분배하는 것을 볼 수 있습니다.

😅 개인적인 실수

처음에 문제를 풀 때 반복문 안에서 배열을 따로 만들어 놓고 나중에 최종적으로 분배가 끝나면 해당 배열을 정답 배열에 반영하는 방법을 썼는데요. 아래 pseudo 코드와 같이요. 이러면 반복문 하나당 enroll의 길이만큼 (최대 10,000)의 연산이 추가적으로 생기는 셈입니다.

이렇게 했던 이유는 현재 분배 대상이 되는 금액을 ans 배열에 저장을 할 수 없었기 때문인데요. 그냥 하나의 변수 하나만 선언하면 해결된 문제인데 이 문제로 시간초과가 되고 말았습니다.

// 판매 건당 도는 반복문
for i in 0..<seller.count {
	// 임시 배열 선언
    var temp = Array(repeating: 0, count: enroll.count)  

	// 추천인에게 분배하는 반복문
    while true {}
		
    // temp에 저장된 금액을 ans에 더하는 반복문
    for money in temp {}
}

코드

func solution(_ enroll:[String], _ referral:[String], _ seller:[String], _ amount:[Int]) -> [Int] {

    // 이름 - 인덱스
    var indexTable = [String:Int]()
    
    for (i, name) in enroll.enumerated() {
        indexTable[name] = i
    }

    // 정답 배열
    var ans = Array(repeating: 0, count: enroll.count)
    
    // 판매 건당 반복
    for (s, a) in zip(seller, amount) {
        var now = indexTable[s]!
        var nowMoney = a * 100
        
        var refer = referral[now]
        var give = nowMoney / 10
        
        // 추천인이 없거나 10%가 원단위 절삭일 때까지 반복
        while refer != "-" && give > 0  {
            // 현재 사람이 90% 먹는다
            ans[now] += nowMoney - give
            
            // 10%는 추천인이 가지고 가서 거기서 다시 분배
            now = indexTable[refer]!
            nowMoney = give
            
            // 새로운 추천인과 추천인이 먹을 돈
            refer = referral[now]
            give = nowMoney / 10
        }
        
        // 반복문이 끝나면 현재 사람이 남은 돈은 먹는다
            // 추천인이 없으면 센터에 떼주고
            // 추천인이 있는데 절삭이면 (= give == 0)이면 다 먹는다
        ans[now] += nowMoney - give
    }
    
    return ans
}