문제 개요
여러 개의 아이템이 주어져 있다고 가정해 봅시다. i번째 아이템은 values[i]라는 값과 labels[i]라는 레이블을 가집니다. 이 아이템들 중에서 부분 집합 S를 선택해야 하며, 다음 두 가지 조건을 만족해야 합니다.
- S에 포함되는 아이템의 개수는 num_wanted 이하여야 합니다.
- 모든 레이블 L에 대해, S에 포함된 해당 레이블을 가진 아이템의 개수는 use_limit 이하여야 합니다.
이때, 조건을 만족하는 부분 집합 S의 값 합계 중 가장 큰 값을 구하는 것이 목표입니다.
예시
예를 들어, 입력이 다음과 같다고 해보겠습니다.
- values = [5, 4, 3, 2, 1]
- labels = [1, 1, 2, 2, 3]
- num_wanted = 3
- use_limit = 1
이 경우 출력은 9가 됩니다. 그 이유는 첫 번째(5), 세 번째(3), 다섯 번째(1) 아이템을 선택하면 각 레이블이 한 번씩만 사용되면서 총합 9를 얻을 수 있기 때문입니다.
해결 접근 방법
이 문제는 그리디(Greedy) 알고리즘으로 해결할 수 있습니다. 핵심 아이디어는 값이 큰 아이템부터 우선적으로 선택하되, 레이블별 사용 횟수 제한을 지키는 것입니다. 단계별로 살펴보면 다음과 같습니다.
- (값, 레이블) 쌍을 저장할 배열 v를 생성합니다.
- values의 길이만큼 반복하며 [values[i], labels[i]]를 v에 삽입합니다.
- v를 값 기준으로 내림차순 정렬합니다.
- ans := 0, use := 빈 딕셔너리(레이블별 사용 횟수 저장), i := 0으로 초기화합니다.
- num_wanted가 0보다 크고 i가 v의 길이보다 작은 동안 반복합니다.
- v[i][1] 레이블이 use에 없다면: num_wanted를 1 감소시키고, ans에 v[i][0]을 더한 뒤, use[v[i][1]] := 1로 설정합니다.
- 그렇지 않고 use[v[i][1]] < use_limit이라면: num_wanted를 1 감소시키고, ans에 v[i][0]을 더한 뒤, use[v[i][1]]을 1 증가시킵니다.
- i를 1 증가시킵니다.
- 반복이 끝나면 ans를 반환합니다.
아래 구현 예시를 통해 더 자세히 이해해 보겠습니다.
구현 예제
class Solution(object):
def largestValsFromLabels(self, values, labels, num_wanted, use_limit):
v = []
for i in range(len(values)):
v.append([values[i],labels[i]])
v = sorted(v,key = lambda v:v[0],reverse=True)
ans = 0
use = {}
i = 0
while num_wanted and i < len(v):
if v[i][1] not in use:
num_wanted -=1
ans+=v[i][0]
use[v[i][1]] = 1
elif use[v[i][1]]<use_limit:
num_wanted -=1
ans+=v[i][0]
use[v[i][1]]+=1
i+=1
return ans
ob = Solution()
print(ob.largestValsFromLabels([5,4,3,2,1],[1,1,2,2,3],3,1))입력
[5,4,3,2,1] [1,1,2,2,3] 3 1
출력
9
복잡도 분석
이 알고리즘의 시간 복잡도는 정렬 과정이 지배적이므로 O(n log n)입니다. 여기서 n은 아이템의 개수입니다. 공간 복잡도는 (값, 레이블) 쌍을 저장하는 배열과 레이블별 사용 횟수를 기록하는 딕셔너리 때문에 O(n)입니다.