숫자 리스트 counts가 주어졌을 때, counts[i]는 유형 i에 속한 항목의 개수를 의미합니다. 또 하나의 값 k도 함께 주어집니다. 우리가 구해야 할 것은, 각 그룹이 반드시 서로 다른 유형의 항목들로만 구성되어야 한다는 조건을 만족하면서 만들 수 있는 크기 k짜리 그룹의 최대 개수입니다.
예를 들어 counts = [2, 3, 5, 3], k = 2가 입력으로 주어진 경우를 살펴보겠습니다. 네 가지 유형의 항목을 각각 a, b, c, d라고 표현하면, 모든 원소가 서로 다른 유형인 크기 2짜리 그룹을 다음과 같이 6개 만들 수 있습니다.
[(c, a), (b, a), (c, b), (c, b), (d, a), (d, a)]
따라서 정답은 6이 됩니다.
해결 접근 방법
이 문제는 이진 탐색(Binary Search)을 활용하면 효율적으로 해결할 수 있습니다. 핵심 아이디어는 "g개의 그룹을 만드는 것이 가능한가?"라는 질문에 대해 가능 여부를 판단하는 함수 possible()을 정의하고, 그룹의 개수 g에 대해 이진 탐색을 수행하는 것입니다.
possible(counts, groups, k) 함수는 다음과 같이 동작합니다.
- 필요한 총 항목 수 required를 groups * k로 계산합니다.
- 각 유형별 항목을 순회하면서, 해당 유형에서 그룹에 배정할 수 있는 항목 수는 min(counts[i], groups, required)입니다. 한 유형에서 한 그룹당 최대 1개씩만 사용할 수 있으므로 한 유형이 기여할 수 있는 최댓값은 groups입니다.
- 배정한 만큼 required에서 차감하고, required가 0이 되면 True를 반환합니다.
- 모든 유형을 확인한 후에도 required가 0이 아니면 False를 반환합니다.
그다음 solve(counts, k) 함수는 그룹 개수 범위 [0, sum(counts)] 사이에서 이진 탐색을 수행하여 가능한 그룹 개수의 최댓값을 찾아 반환합니다.
구현 예제
아래 구현을 통해 더 잘 이해해 보겠습니다.
def possible(counts, groups, k):
required = groups * k
for i in range(len(counts)):
temp = min(counts[i], groups, required)
required -= temp
if required == 0:
return True
return False
def solve(counts, k):
res = 0
l = 0
r = sum(counts)
while l <= r:
m = l + (r - l) // 2
if possible(counts, m, k):
l = m + 1
res = max(res, m)
else:
r = m - 1
return res
counts = [2, 3, 5, 3]
k = 2
print(solve(counts, k))입력
[2, 3, 5, 3], 2
출력
6
복잡도 분석
이진 탐색의 범위는 전체 항목 수 N이므로 O(log N)번의 탐색이 발생하고, 각 탐색마다 possible() 함수가 유형의 개수 M에 비례하는 시간이 걸립니다. 따라서 전체 시간 복잡도는 O(M log N)이며, 추가 공간은 상수 수준으로 매우 효율적인 알고리즘입니다.