1. 문제 설명
- 점심시간에 도둑이 들어, 일부 학생이 체육복을 도난당했습니다. 다행히 여벌 체육복이 있는 학생이 이들에게 체육복을 빌려주려 합니다. 학생들의 번호는 체격 순으로 매겨져 있어, 바로 앞 번호의 학생이나 바로 뒷 번호의 학생에게만 체육복을 빌려줄 수 있습니다. 예를 들어, 4번 학생은 3번 학생이나 5번 학생에게만 체육복을 빌려줄 수 있습니다. 체육복이 없으면 수업을 들을 수 없기 때문에 체육복을 적절히 빌려 최대한 많은 학생이 체육 수업을 들어야 합니다.
- 전체 학생의 수 n, 체육복을 도난당한 학생들의 번호가 담긴 배열 lost, 여벌의 체육복을 가져온 학생들의 번호가 담긴 배열 reserve가 매개변수로 주어질 때, 체육 수업을 들을 수 있는 학생의 최댓값을 return 하도록 solution 함수를 작성해주세요.
2. 제한사항
- 전체 학생의 수는 2명 이상 30명 이하입니다.
- 체육복을 도난당한 학생의 수는 2명 이상 n명 이하이고 중복되는 번호는 없습니다.
- 여벌의 체육복을 가져온 학생의 수는 1명 이상 n명 이하이고 중복되는 번호는 없습니다.
- 여벌 체육복이 있는 학생만 다른 학생에게 체육복을 빌려줄 수 있습니다.
- 여벌 체육복을 가져온 학생이 체육복을 도난당했을 수 있습니다. 이때 이 학생은 체육복을 하나만 도난당했다고 가정하며, 남은 체육복이 하나이기에 다른 학생에게는 체육복을 빌려줄 수 없습니다.
3. 입출력 예
| n | lost | reserve | return |
|---|---|---|---|
| 5 | [2, 4] | [1, 3, 5] | 5 |
=> 1번 학생이 2번 학생에게 체육복을 빌려주고, 3번 학생이나 5번 학생이 4번 학생에게 체육복을 빌려주면 학생 5명이 체육 수업을 들을 수 있습니다.
| n | lost | reserve | return |
|---|---|---|---|
| 5 | [2, 4] | [3] | 4 |
=> 3번 학생이 2번 학생이나 4번 학생에게 체육복을 빌려주면 학생 4명이 체육 수업을 들을 수 있습니다.
| n | lost | reserve | return |
|---|---|---|---|
| 3 | [3] | [1] | 2 |
=> 2번 또는 4번 학생이 여벌 체육복을 갖고 있지 않기 때문에 3번 학생은 체육 수업을 들을 수 없고 학생 2명이 체육 수업을 들을 수 있습니다.
4. 문제 풀이
1) Greedy Algorithm (dictionary)
-
알고리즘의 각 단계에서 그 순간에 최적이라고 생각되는 것을 선택
-
정해진 순서에 우선하여 빌려줄 방향을 정해야 함
-
전체 학생 수는 최대 30명으로 적은 편
-
학생 수만큼 배열을 확보하고 각 학생이 갖고 있는 체육복 수를 저장
-
번호 순서대로 배열을 스캔하면서 빌려줄 관계를 정함
def solution(n, lost, reserve):
u = [1] * (n + 2) # 1로 초기화, 맨 앞과 맨 뒤도 추가
for i in reserve:
u[i] += 1
for i in lost:
u[i] -= 1
for i in range(1, n + 1):
# 앞 사람이 체육복이 없고, 내가 여벌을 갖고 있다면
if u[i - 1] == 0 and u[i] == 2:
u[i - 1:i + 1] = [1, 1] # i - 1과 i번 원소를 1로 만듦
# 뒷 사람이 체육복이 없고, 내가 여벌을 갖고 있다면
elif u[i] == 2 and u[i + 1] == 2:
u[i:i + 2] = [1, 1]
return len([x for x in u[1:-1] if x > 0]) # 체육복이 있는 학생 수
- 여벌을 가져온 학생을 처리하는 과정은 reserve의 길이에 비례
- 체육복을 잃어버린 학생을 처리하는 과정은 lost의 길이에 비례
- 체육복 빌려주는 것을 처리하는 과정은 전체 학생 수인 n에 비례
- 알고리즘의 복잡도는 O(n)
=> 전체 학생 수가 너무 크면 복잡해짐
2) + sort, set 이용
- 만약 여벌의 체육복을 가져온 학생이 매우 적다면, 여벌을 가져오지 않은 학생을 탐색하는 횟수가 더 많아지는 단점이 있음
- 여벌의 체육복을 가져온 학생들의 번호인 reserve를 정렬하고, 순서대로 살펴보면서 빌려줄 수 있는 다른 학생이 있는지 확인 후 처리함
def solution(n, lost, reserve):
s = set(lost) & set(reserve) # 체육복을 가져왔는데 도난당한 학생들
l = set(lost) - s # 체육복을 도난당한 학생 중 빌려야 하는 학생들
r = set(reserve) - s # 여벌의 체육복을 빌려줄 수 있는 학생들
for x in sorted(r):
if x - 1 in l:
l.remove(x - 1)
elif x + 1 in l:
l.remove(x + 1)
return n - len(l)def solution(n, lost, reserve):
lost_set = set(lost) - set(reserve)
reserve_set = set(reserve) - set(lost)
for i in reserve_set:
if i - 1 in lost_set:
lost_set.remove(i - 1)
elif i + 1 in lost_set:
lost_set.remove(i + 1)
answer = n - len(lost_set)
return answer
- 전체 학생 수인 n은 그대로인데 여벌의 체육복을 가져온 학생 수인 k가 훨씬 더 적으면 유리한 방식임
=> reserve 정렬 : O(klogk)- 빌려줄 수 있는 다른 학생을 찾는 것은 해시를 사용해서 상수 시간에 처리할 수 있음
=> 체육복을 빌려줄 수 있는 학생 확인 후 처리 : O(k) * O(1)- 전체 알고리즘 시간 복잡도 O(klogk)
Backend development