문제 링크

문제 풀이 아이디어

완전 탐색

users의 길이 최대 100, 할인 비율 종류 4개 (10%, 20%, 30%, 40%), 이모티콘의 종류가 최대 7가지로 단촐한 N을 가진 문제입니다. 이모티콘 x 할인의 모든 케이스를 구해도 4^7이고 여기에 users의 길이를 곱하면 1638400에 불과합니다. 따라서 완전탐색으로 풀어도 무방한 문제입니다.

또한 시간복잡도를 줄이려고 다른 알고리즘을 사용하려고 해도 이모티콘의 각각의 할인율이 다를 수 있고 user별도 다 따져봐야하므로 완전 탐색 외에는 방법이 없습니다.

모든 케이스 구하기 → dfs (재귀)

가장 먼저 해야하는 일은 모든 이모티콘에 대해서 모든 할인율을 매칭해서 판매 케이스들을 만드는 것입니다. 모든 이모티콘은 각각의 할인율을 가지고 할인율은 중복이 가능합니다. 저는 재귀를 활용한 dfs로 구현했습니다.

여기까지 모든 조합을 구하면 각각의 판매케이스에 대해서 user들이 구매할지 안할지 결정해서 user 별로 필요한 금액을 구하고 user의 리미트를 초과하면 이모티콘 플러스를 가입시키면 됩니다.

정렬

이렇게 모든 케이스에 대해서 이모티콘 플러스 가입자와 이모티콘 판매액이 정해졌으면 이 케이스들의 결과를 플러스 가입자 순, 가입자가 동일하다면 판매액 순으로 정렬해서 가장 앞에 오는 값을 리턴하면 됩니다.

코드

// 이모티콘, 할인율의 쌍을 나타내는 구조체
struct Sell {
    let emoticon: Int
    let discount: Int
    
    // 할인율을 감안한 이모티콘 가격
    var price: Int {
        Int(emoticon * (100 - discount) / 100)
    }
}

// 이모티콘 종류 x 할인율의 조합을 구하는 함수
func combination(emoticons: [Int]) -> [[Sell]] {
    
    // 모든 케이스를 리턴할 배열
    var result = [[Sell]]()
    
    // 할인율
    let discounts = [10, 20, 30, 40]
    
    // 재귀함수 구현
    func combi(now: [Sell]) {
        // 탈출 조건
        if now.count == emoticons.count {
            result.append(now)
            return
        }
        
        // 다음 이모티콘의 index
        let next = now.count
        
        // 할인율은 중복 가능하므로 10 ~ 40까지 모든 케이스에 대해서 탐색
        for i in 0..<4 {
            var now = now
            now.append(Sell(emoticon: emoticons[next], discount: discounts[i]))
            combi(now: now)
        }
    }
    
    combi(now: [])
    
    return result
}

func solution(_ users:[[Int]], _ emoticons:[Int]) -> [Int] {
    // 결과 배열: [가입자수, 판매액]
    var results = [[Int]]()
    
    // 모든 이모티콘-할인율 조합 구하기
    let sellCases = combination(emoticons: emoticons)
    
    // 모든 케이스에 대해서
    for sells in sellCases {
        // 각 user별 구매액: sales[i] = users[i]의 이모티콘 구매 금액
        var sales = Array(repeating: 0, count: users.count)
        // 모든 이모티콘에 대해서 구매 여부 결정
        for i in 0..<sells.count {
            for j in 0..<users.count {
                // 원하는 할인율 이상이면 구입
                if users[j][0] <= sells[i].discount {
                    sales[j] += sells[i].price
                }
            }
        }
        // 결과 배열: [가입자수, 판매액]
        var result = [0, 0]
        
        for i in 0..<sales.count {
            // 원하는 금액 이상이면 이모티콘 플러스 가입
            if sales[i] >= users[i][1] {
                result[0] += 1
            // 원하는 금액 이하면 그냥 구입
            } else {
                result[1] += sales[i]
            }
        }
        results.append(result)
    }
    
    // 가입자수, 판매액 기준 내림차순으로 정렬
    results.sort { r1, r2 in
        if r1[0] == r2[0] {
            return r1[1] > r2[1]
        } else {
            return r1[0] > r2[0]
        }
    }
    
    return results[0]
}