(중복순열 3가지 방법) 이모티콘 할인행사

문제 링크

카카오 코딩테스트: 이모티콘 할인행사

문제 분석

먼저 이 문제는 중복순열을 활용해야 하는 문제로서, 각 이모티콘마다 rates 적용한 경우의 수에서,

문제에 제시된 두 목표일 때의, (이모티콘 플러스 서비스 가입 수와 이모티콘 매출액) 값을 갱신시켜나가야 하는 문제다.

이 문제의 경우, 중복순열을 여러가지 방법으로 구현해보는 연습을 해보았다.

특히 비트마스킹의 경우, 지금까지 2^n 가지 경우의 수 문제. 즉 2가지 선택을 n번 반복하는 경우에 대해서, 적용하는 문제에만 적용해왔는데, 4^n 의 경우에는 1비트가 아니라 2비트를 사용하기에 이렇게도 코드를 짤 수 있구나. 생각해볼 수 있던 문제였다.

물론, 4진법을 활용해서도 풀어보았다.

구현하기에는 재귀방법이 가장 간단하고 빠르다. 그러나 학습을 위해 다양한 방법으로 문제를 풀어보았다.

내 코드

재귀방법

import Foundation

func solution(_ users:[[Int]], _ emoticons:[Int]) -> [Int] {
    var maxPlus = 0, maxSales = 0
    let rates = [10, 20, 30, 40]
    
    func combi(_ idx: Int, _ cur: [Int]) {
        if idx == emoticons.count {
            go(cur)
            return
        }
        
        for rate in rates {
            combi(idx + 1, cur + [rate])
        }
    }
    
    func go(_ discounts: [Int]) {
        var curPlus = 0
        var curSales = 0
        
        for user in users {
            let userRate = user[0]
            var userMoney = user[1]
            var userTotalSales = 0
            
            for i in 0..<emoticons.count {
                if userRate <= discounts[i] {
                    userTotalSales += emoticons[i] * (100 - discounts[i]) / 100
                }
            }
            
            if userMoney <= userTotalSales {
                curPlus += 1
            } else {
                curSales += userTotalSales
            }
        }
        
        // 해당 조합에서, maxPlus, maxSales 업데이트
        if maxPlus < curPlus || (maxPlus == curPlus && maxSales < curSales) {
            maxPlus = curPlus
            maxSales = curSales
        }
    }
    
    combi(0, [])
    
    return [maxPlus, maxSales]
}

4진법 활용

import Foundation

func solution(_ users:[[Int]], _ emoticons:[Int]) -> [Int] {
    let rates = [10, 20, 30, 40]
    let n = emoticons.count
    
    var maxPlusCount = 0
    var maxSales = 0
    
    func go(_ discounts: [Int]) {
        var curSales = 0
        var curPlusCount = 0
        
        for user in users {
            let userDiscount = user[0]
            let userTotalMoney = user[1]
            var userTotalSales = 0
            var plus = false
            
            for (discount, emoticonCost) in zip(discounts, emoticons) {
                if userDiscount > discount { continue }
                userTotalSales += emoticonCost * (100 - discount) / 100
                if userTotalSales >= userTotalMoney {
                    plus = true
                    userTotalSales = 0
                    break
                }
            }
            if plus { curPlusCount += 1 }
            curSales += userTotalSales
        }
        
        // 현재 이모티콘 플러스 가입자수가 더 많다면 업데이트
        if maxPlusCount < curPlusCount {
            maxPlusCount = curPlusCount
            maxSales = curSales
        }
        // 그게 아니라면, 가입자수는 같고 현재 판매액이 더 크다면 업데이트
        else if maxPlusCount == curPlusCount && maxSales < curSales {
            maxPlusCount = curPlusCount
            maxSales = curSales
        }
        // 그외는 업데이트 x
    }
    
    let totalCases = Int(pow(4.0, Double(n)))   // 1 << (2 * n)과 동일
    
    for i in 0..<totalCases {
        var discounts = [Int]()
        var num = i
        
        for _ in 0..<n {
            discounts.append(rates[num % 4])
            num /= 4
        }
        
        go(discounts)
    }
    
    return [maxPlusCount, maxSales]
}

비트마스킹

import Foundation

func solution(_ users:[[Int]], _ emoticons:[Int]) -> [Int] {
    let rates = [10, 20, 30, 40]
    let n = emoticons.count
    
    var maxPlusCount = 0
    var maxSales = 0
    
    func go(_ discounts: [Int]) {
        var curSales = 0
        var curPlusCount = 0
        
        for user in users {
            let userDiscount = user[0]
            let userTotalMoney = user[1]
            var userTotalSales = 0
            var plus = false
            
            for (discount, emoticonCost) in zip(discounts, emoticons) {
                if userDiscount > discount { continue }
                userTotalSales += emoticonCost * (100 - discount) / 100
                if userTotalSales >= userTotalMoney {
                    plus = true
                    userTotalSales = 0
                    break
                }
            }
            if plus { curPlusCount += 1 }
            curSales += userTotalSales
        }
        
        // 현재 이모티콘 플러스 가입자수가 더 많다면 업데이트
        if maxPlusCount < curPlusCount {
            maxPlusCount = curPlusCount
            maxSales = curSales
        }
        // 그게 아니라면, 가입자수는 같고 현재 판매액이 더 크다면 업데이트
        else if maxPlusCount == curPlusCount && maxSales < curSales {
            maxPlusCount = curPlusCount
            maxSales = curSales
        }
        // 그외는 업데이트 x
    }

    for mask in 0..<(1 << (2 * n)) {
        var discounts = [Int]()
        
        for i in 0..<n {
            let shift = i * 2
            let value = (mask >> shift) & 0b11  // 2비트 추출
            discounts.append(rates[value])
        }
        
        go(discounts)
    }
    
    return [maxPlusCount, maxSales]
}

배운 점

리팩토링 코드

import Foundation

func solution(_ users:[[Int]], _ emoticons:[Int]) -> [Int] {
    let rates = [10, 20, 30, 40]
    let n = emoticons.count
    
    var maxPlusCount = 0
    var maxSales = 0
    
    func go(_ discounts: [Int]) {
        var curSales = 0
        var curPlusCount = 0
        
        for user in users {
            let userDiscount = user[0]
            let userTotalMoney = user[1]
            var userTotalSales = 0
            
            for (discount, emoticonCost) in zip(discounts, emoticons) {
                if userDiscount > discount { continue }
                let discounted = emoticonCost * (100 - discount) / 100
                userTotalSales += discounted
                if userTotalSales >= userTotalMoney {
                    curPlusCount += 1
                    userTotalSales = 0
                    break
                }
            }
            curSales += userTotalSales
        }
        
        // 현재 이모티콘 플러스 가입자수가 더 많다면 업데이트
        // 그게 아니라면, 가입자수는 같고 현재 판매액이 더 크다면 업데이트
        // 그외는 업데이트 x
        if (maxPlusCount, maxSales) < (curPlusCount, curSales) {
            maxPlusCount = curPlusCount
            maxSales = curSales
        }
    }

    for mask in 0..<(1 << (2 * n)) {
        var discounts = [Int]()
        
        for i in 0..<n {
            let shift = i * 2
            let value = (mask >> shift) & 0b11  // 2비트 추출
            discounts.append(rates[value])
        }
        
        go(discounts)
    }
    
    return [maxPlusCount, maxSales]
}

튜플 비교를 통해서, 기존의 긴 조건문을 한줄로 바꿈!
zip 사용

정리

이 문제는 시간복잡도는 중복순열 전체 경우의 수는 4^n (n: emoticons.count, 최대 7)

각 경우마다, m명에 대해 n개의 이모티콘 확인 (m: users.count, 최대 100)

전체 시간복잡도 O(4^n * mn)

최대 (4의 7승 곱하기 700, 약 1100만)