[Algorithm] 이모티콘 할인행사

[hwangJi-dev]

💬 문제

[코딩테스트 연습 - 이모티콘 할인행사](https://school.programmers.co.kr/learn/courses/30/lessons/150368)

💬 Idea

1. 먼저 이모티콘 수에 맞는 할인율 조합을 구하자
   1. 어떻게 구할 것인가? → dfs 재귀함수를 만들어서 10, 20, 30, 40 각각을 돌며 array에 더한다.
      1. dfs 비교군을 줄이기 위해 user가 갖고 있는 가격 기준의 최저값을 구해 sales를 먼저 필터링해준다.
      2. ex. user = [[40, 10000], [25, 10000]] 의 경우 유저들이 구입할 최저 세일 비율이 30% 이므로 30, 40 만을 갖고 가격 조합을 만들어줄 수 있다. → 시간 절약 !
2. 할인율 조합을 구한 뒤 해당 조합에서 이모티콘플러스 가입자 수와 판매액이 최댓값인지를 비교하자

💬 풀이

1. 첫번째 시도 - 시간초과 [정확성 (75/100)]

   var percentArr: Set<[Int]> = []
   func solution(users:[[Int]], emoticons:[Int]) -> [Int] {
    dfs(index: 0, arr: [], max: emoticons.count)
    
    var emtiplusCnt = 0
    var sumSale = 0
    
    for percent in percentArr {
    var cnt = 0
    var sum = 0
    
    for user in users {
    var userSum = 0
    
    for (index, p) in percent.enumerated() {
    // 유저의 기준비율에 맞는 이모티콘만 선별하기
    if p >= user[0] {
    userSum += calDiscountPrice(Double(emoticons[index]), Double(p))
    }
    }
    
    // 유저의 기준가격을 넘긴다면 이모티콘 플러스 가입시키기
    if userSum >= user[1] {
    cnt += 1
    } else {
    sum += userSum
    }
    }
    
    if cnt > emtiplusCnt {
    emtiplusCnt = cnt
    sumSale = sum
    } else if cnt == emtiplusCnt {
    sumSale = sum > sumSale ? sum : sumSale
    }
    }
    
    return [emtiplusCnt, sumSale]
   }
   
   func dfs(index: Int, arr: [Int], max: Int) {
    if index == max {
    percentArr.insert(arr)
    return
    }
    
    for _ in 0..<max {
    dfs(index: index + 1, arr: arr + [10], max: max)
    dfs(index: index + 1, arr: arr + [20], max: max)
    dfs(index: index + 1, arr: arr + [30], max: max)
    dfs(index: index + 1, arr: arr + [40], max: max)
    }
   }
   
   // 이모티콘 할인 가격 계산
   func calDiscountPrice(_ origin: Double, _ percent: Double) -> Int {
    return Int(origin - ((origin / 100) * percent))
   }

   • 이모티콘 할인율 조합을 구하는 dfs부분에서 문제가 있다고 판단했음

2. 두번째 시도 - dfs 부분 불필요한 코드 제거 → 정답

   1. 최저 0.25 / 최고 3721.27

   var percentArr: [[Int]] = []
   func solution(_ users:[[Int]], _ emoticons:[Int]) -> [Int] {
    let users = users.sorted(by: { $0[0] > $1[0] })
    let sales = [10, 20, 30, 40].filter({ $0 >= users.last![0] })
    
    // 이모티콘의 할인가격 배열 구하기
    dfs(index: 0, arr: [], max: emoticons.count, sales: sales)
    
    var finalEmtiPlusCnt = 0
    var finalSum = 0
    
    for percent in Set(percentArr) {
    var emtiplusCnt = 0
    var sum = 0
    
    for user in users {
    var userSum = 0
    
    for (index, p) in percent.enumerated() {
    // 유저의 기준비율에 맞는 이모티콘만 선별하기
    if p >= user[0] {
    userSum += calDiscountPrice(emoticons[index], p)
    }
    }
    
    // 유저의 기준가격을 넘긴다면 이모티콘 플러스 가입
    if userSum >= user[1] {
    emtiplusCnt += 1
    } else {
    sum += userSum
    }
    }
    
    // 현재 할인 비율 모음이 최대 이모티콘 플러스 가입자를 이끌어내는지 확인
    if emtiplusCnt > finalEmtiPlusCnt {
    finalEmtiPlusCnt = emtiplusCnt
    finalSum = sum
    } else if emtiplusCnt == finalEmtiPlusCnt {
    finalSum = sum > finalSum ? sum : finalSum
    }
    }
    
    return [finalEmtiPlusCnt, finalSum]
   }
   
   func dfs(index: Int, arr: [Int], max: Int, sales: [Int]) {
    if index == max {
    percentArr.append(arr)
    return
    }
    
    for sale in sales {
    dfs(index: index + 1, arr: arr + [sale], max: max, sales: sales)
    }
   }
   
   // 이모티콘 할인 가격 계산
   func calDiscountPrice(_ origin: Int, _ percent: Int) -> Int {
    return origin - ((origin / 100) * percent)
   }

• 3중 중첩 for문을 제거하고 2중 for문으로 대체한 풀이.

• dfs에서 조합을 구할 때마다 해당 할인가격 조합의 이모티콘플러스 가입자 수와 판매액이 최댓값인지 비교하기

  • 최저 0.22 / 최고 3809.28

  var finalEmtiPlusCnt = 0
  var finalSum = 0
  var user: [[Int]] = []
  var emoticon: [Int] = []
  
  func solution(users:[[Int]], emoticons:[Int]) -> [Int] {
   user = users
   emoticon = emoticons
   
   dfs(index: 0, arr: [], max: emoticons.count, sales: [10, 20, 30, 40])
   
   return [finalEmtiPlusCnt, finalSum]
  }
  
  func dfs(index: Int, arr: [Int], max: Int, sales: [Int]) {
   // 이모티콘의 할인가격 조합 도출
   if index == max {
   // 해당 할인가격 조합의 이모티콘플러스 가입자 수와 판매액이 최댓값인지 비교
   getResultBySalesComb(arr)
   return
   }
   
   for sale in sales {
   dfs(index: index + 1, arr: arr + [sale], max: max, sales: sales)
   }
  }
  
  // 이모티콘플러스 가입자 수와 판매액 도출 후 최댓값인지 비교하는 메서드
  func getResultBySalesComb(_ arr: [Int]) {
   var emtiplusCnt = 0
   var sum = 0
   
   for u in user {
   var userSum = 0
   
   for (index, p) in arr.enumerated() {
   // 유저의 기준비율에 맞는 이모티콘만 선별
   if p >= u[0] {
   userSum += calDiscountPrice(emoticon[index], p)
   }
   }
   
   // 유저의 기준가격을 넘긴다면 이모티콘 플러스 가입
   if userSum >= u[1] {
   emtiplusCnt += 1
   } else {
   sum += userSum
   }
   }
   
   // 현재 할인 비율 모음이 최대 이모티콘 플러스 가입자를 이끌어내는지 확인
   if emtiplusCnt > finalEmtiPlusCnt {
   finalEmtiPlusCnt = emtiplusCnt
   finalSum = sum
   } else if emtiplusCnt == finalEmtiPlusCnt {
   finalSum = sum > finalSum ? sum : finalSum
   }
  }
  
  // 이모티콘 할인 가격 계산 메서드
  func calDiscountPrice(_ origin: Int, _ percent: Int) -> Int {
   return origin - ((origin / 100) * percent)
  }

• dfs 부분 불필요한 코드 제거 && 고차함수 사용하여 비교군 감소

  • 최저 0.34 / 최고 3551.96

  var finalEmtiPlusCnt = 0
  var finalSum = 0
  var user: [[Int]] = []
  var emoticon: [Int] = []
  
  func solution(users:[[Int]], emoticons:[Int]) -> [Int] {
   user = users.sorted(by: { $0[0] > $1[0] })
   emoticon = emoticons
   
   dfs(index: 0, arr: [], max: emoticons.count, sales: [10, 20, 30, 40].filter({ $0 >= user.last![0] }))
   
   return [finalEmtiPlusCnt, finalSum]
  }
  
  func dfs(index: Int, arr: [Int], max: Int, sales: [Int]) {
   // 이모티콘의 할인가격 조합 도출
   if index == max {
   // 해당 할인가격 조합의 이모티콘플러스 가입자 수와 판매액이 최댓값인지 비교
   getResultBySalesComb(arr)
   return
   }
   
   for sale in sales {
   dfs(index: index + 1, arr: arr + [sale], max: max, sales: sales)
   }
  }
  
  // 이모티콘플러스 가입자 수와 판매액 도출 후 최댓값인지 비교하는 메서드
  func getResultBySalesComb(_ arr: [Int]) {
   var emtiplusCnt = 0
   var sum = 0
   
   for u in user {
   var userSum = 0
   
   for (index, p) in arr.enumerated() {
   // 유저의 기준비율에 맞는 이모티콘만 선별
   if p >= u[0] {
   userSum += calDiscountPrice(emoticon[index], p)
   }
   }
   
   // 유저의 기준가격을 넘긴다면 이모티콘 플러스 가입
   if userSum >= u[1] {
   emtiplusCnt += 1
   } else {
   sum += userSum
   }
   }
   
   // 현재 할인 비율 모음이 최대 이모티콘 플러스 가입자를 이끌어내는지 확인
   if emtiplusCnt > finalEmtiPlusCnt {
   finalEmtiPlusCnt = emtiplusCnt
   finalSum = sum
   } else if emtiplusCnt == finalEmtiPlusCnt {
   finalSum = sum > finalSum ? sum : finalSum
   }
  }
  
  // 이모티콘 할인 가격 계산 메서드
  func calDiscountPrice(_ origin: Int, _ percent: Int) -> Int {
   return origin - ((origin / 100) * percent)
  }