작업 목록과 사람 목록이 각각 주어져 있다고 가정해 보겠습니다. tasks[i]는 i번째 작업을 수행하는 데 필요한 힘의 양을 나타내고, people[i]는 i번째 사람이 가지고 있는 힘의 양을 나타냅니다. 이때 한 사람은 최대 하나의 작업만 수행할 수 있다는 조건 하에서, 완료할 수 있는 작업의 총 개수를 구하는 것이 이 글의 목표입니다.
예를 들어 입력이 tasks = [4, 3, 9, 15], people = [10, 5, 3, 2]라고 한다면 출력은 3이 됩니다. 첫 번째 사람은 힘이 10이므로 작업 9를 수행할 수 있고, 두 번째 사람은 힘이 5이므로 작업 4를, 세 번째 사람은 힘이 3이므로 작업 3을 수행할 수 있습니다. 반면 네 번째 사람은 힘이 2뿐이라 어떤 작업도 수행할 수 없습니다.
문제 해결 접근 방법
이 문제는 그리디(Greedy) 알고리즘으로 효율적으로 해결할 수 있습니다. 핵심 아이디어는 두 목록을 모두 오름차순으로 정렬한 뒤, 힘이 약한 사람부터 자신이 감당할 수 있는 가장 작은 작업에 순서대로 배정하는 것입니다. 이렇게 하면 상대적으로 강한 사람들이 더 어려운 작업을 수행할 기회를 유지하게 되어, 전체 완료 작업 수를 최대화할 수 있습니다.
구체적인 해결 단계는 다음과 같습니다.
- tasks 리스트와 people 리스트를 각각 정렬합니다.
- 완료된 작업 수를 세는 변수 ct와 현재 확인 중인 작업 위치를 가리키는 ind를 0으로 초기화합니다.
- i를 0부터 people의 크기까지 반복하면서 다음을 수행합니다.
- j를 ind부터 tasks의 크기까지 반복합니다.
- 만약 people[i] >= tasks[j]라면, 해당 사람이 이 작업을 수행할 수 있으므로 ct를 1 증가시키고 ind도 1 증가시킨 후 내부 루프를 빠져나갑니다.
- 그렇지 않다면, 현재 사람이 남은 어떤 작업도 수행할 수 없다는 의미이므로 즉시 루프를 빠져나갑니다.
- j를 ind부터 tasks의 크기까지 반복합니다.
- 모든 반복이 끝나면 ct를 반환합니다.
구현 예제
아래 코드를 통해 실제 동작을 더 잘 이해할 수 있습니다.
class Solution:
def solve(self, tasks, people):
tasks.sort()
people.sort()
ct = 0
ind = 0
for i in range(len(people)):
for j in range(ind, len(tasks)):
if people[i] >= tasks[j]:
ct += 1
ind += 1
break
else:
break
return ct
ob = Solution()
tasks = [4, 3, 9, 15]
people = [10, 5, 3, 2]
print(ob.solve(tasks, people))
입력
[4, 3, 9, 15], [10, 5, 3, 2]
출력
3
시간 복잡도 분석
두 리스트를 정렬하는 데 각각 O(n log n)과 O(m log m)의 시간이 걸리며, 이후 사람과 작업을 매칭하는 과정은 두 포인터처럼 한 번씩만 진행되므로 O(n + m)입니다. 따라서 전체 시간 복잡도는 O(n log n + m log m)이며, 이는 대규모 입력에서도 효율적으로 동작합니다.