프로그래머스 150368 이모티콘 할인 행사 - Lv2

문제 링크

https://school.programmers.co.kr/learn/courses/30/lessons/150368

문제 요약

• n 명의 유저에게 m 개의 이모티콘을 할인해서 판매하는 행사를 함.
• 조건 1 : 유저들은 일정 비율 이상 할인하는 이모티콘들을 모두 구매하고, 그 구매 가격이 일정 가격을 넘을 경우 이모티콘을 무제한으로 쓸 수 있는 이모티콘 플러스에 가입한다고 가정

  • 예를 들어 유저 1과 2는 다음과 같을 수 있음

    	비율	가격
    1	40	10000
    2	25	9000

    유저 1은 할인율이 40% 이상인 모든 이모티콘을 구매하고, 그 구매 가격 총합이 10000을 넘기면 이모티콘 플러스에 가입을 한다.

    유저 2는 할인율이 25% 이상인 모든 이모티콘을 구매하고, 그 구매 가격 총합이 9000을 넘기면 이모티콘 플러스에 가입을 한다.

• 조건 2 : 각 이모티콘의 할인율은 10, 20, 30, 40% 중 하나로 설정할 수 있고, 서로 다를 수 있음
• 행사 목표 : 이모티콘 플러스 가입자를 늘리고(1), 이모티콘 판매액을 늘리는 것(2). (1 > 2)
• answer : 행사 목표를 최대한 달성했을 때 이모티콘 플러스 가입자 수와 이모티콘 판매액

문제 분석 과정

• 이모티콘 할인율은 최대 7차원짜리 벡터인데, 이 벡터들은 특정 인자를 바꾸면서 서로를 오갈 수 있음

  • 예 : (10, 10, 10) ↔ (10, 20, 10)

    ⇒ 그래프로 표현 가능함

• answer을 찾으려면 가능한 이모티콘 할인율를 모두 찾아보면서 최대값을 확인해야 함 ⇒ 그래프 탐색으로 생각할 수 있음
  
• 할인율을 한 번만 확인하면 되므로 DFS/BFS를 쓸 수는 있지만, 문제는 이 경우 visited 값 표시하기가 힘듦 ⇒ 따라서 그냥 (10, 10, 10) 같은 할인율 값을 trace로 해석하고 back tracking을 하는게 좋을듯?
  
• 경우의 수가 4 ** 7 = 4000 이라 쌩으로 다 하기에는 억울하니 탈출 조건 새워야 할듯 ⇒ 근데 이거 세울 수가 있나? 너무 규칙이 어려운데 (이때 완전 탐색이라는 걸 눈치채야 했음)
  ⇒ ???
  ⇒ 일단 그리디로 풀 수 있는 계열은 아닌 거 같은데? (이모티콘 가격 큰 순서대로 할인율 조절한다고 정답은 아님)
  ⇒ 그렇다고 DP로 풀자니 작은 문제의 해답이 큰 문제의 해답과 연관이 없는듯?
  ⇒ 수학 문제인가? 아니 근데 계산 방식이 단순해서 굳이 수학을 들고 와야 하나?
  ⇒ 이거 그냥 전부 탐색하고, 자료구조나 구현 쪽으로 속도를 올려야 할 거 같은데? (이 생각을 해서 코드 수행 시간을 대폭 단축함)

풀이 전략

• 자료구조나 구현을 이용해서 빠르게 완전 탐색을 하자

  • 이모티콘 할인율을 조정할 때마다 모든 유저에 대해서 더하고 구독 가격을 넘겼는지 확인하는 방식으로 코드를 짜면 너무 오래 걸린다.

    • 4 ^ 7 (할인율 경우의 수) X 유저의 수 (최대 100명) X 2 (할인율 확인 + 구독 가격 넘겼는지 확인)

    ⇒ 할인율 확인을 반복하지 않기 위해 users를 테이블(2중 리스트)로 구조를 바꾸자

    ⇒ 비슷한 할인율을 가진 user들의 emoticon 구입 총액은 같으니 그냥 4차원 벡터에 저장하자

    ⇒ users 전체에서 구독 비용을 넘었는지 확인하지 말고 테이블 가로 끝부터 확인하자

    Ind
    0	5900
    1	5200
    2	9200	10000
    3	2900	3100	6900

    10%~	20%~	30%~	40%~
    2000	3000	3000	3500

    연산 횟수 ≤ 4 ** 7 (할인율 경우의 수) X 유저의 수 (최대 100명)

의사 코드

table <-  테이블(2중 리스트). 
					table[i]에는 할인율 (i) * 10% ~ (i+1) * 10%의 user들이 정렬되어 저장  

def bt(s = [0, 0, 0, 0], change = 0):
		s <- 할인율 별 이모티콘 구입 총액
		change <- 할인율을 설정할 이모티콘 index
		answer <- 기존의 정답
		
		if change == len(emoticons): # 마지막 이모티콘까지 할인율을 설정했다면
				s로 테이블 가로 끝부터 탐색하면서 new_answer를 계산
				answer = max(answer, new_answer)
				return
		
		for sale in range(1,5): # 1 -> 10%, 2 -> 20% ...
				new_s = s.copy()
				for i in range(sale):
						# 만약에 sale이 3이면 index 3(40%)에서는 값을 추가 안 함
						new_s[i] += emoticons[change] * (10 - sale) // 10
				bt(new_s, change + 1)
		
print(answer)

코드

class bt:
    def __init__(self, users, emoticons):
        self.answer = [0,0]
        
        users.sort(key = lambda x : x[1])
        self.table = [[] for _ in range(4)]
        for user in users:
            i = user[0]//10 if user[0]%10 != 0 else user[0]//10 - 1
            self.table[i].append(user[1])
            
        self.users = users
        self.emoticons = emoticons
    
    def bt_(self, s = [0, 0, 0, 0], change = 0):
        if change == len(self.emoticons):
            self.check(s)
            return
        
        for sale in range(1, 5):
            new_s = s.copy()
            for i in range(sale):
                new_s[i] += self.emoticons[change] * (10 - sale) // 10
            
            self.bt_(new_s, change + 1)
    
    def check(self, s):
        new_answer = [0, 0]
        for i in range(4):
            count = len(self.table[i])
            for user_price in reversed(self.table[i]):
                if s[i] >= user_price :
                    break
                count -= 1
            
            new_answer[0] += count
            new_answer[1] += (len(self.table[i]) - count) * s[i]
        
        self.answer = max(new_answer, self.answer)
        
def solution(users, emoticons):
    back_tracking = bt(users, emoticons)
    back_tracking.bt_()
    
    return back_tracking.answer

위의 코드 실행 결과 (타 제출자의 코드보다 최대 18배 빠름 )

다른 사람 코드 실행 결과