lv1 체육복

❓문제 설명

---

• 점심시간에 도둑이 들어, 일부 학생이 체육복을 도난당했습니다. 다행히 여벌 체육복이 있는 학생이 이들에게 체육복을 빌려주려 합니다. 학생들의 번호는 체격 순으로 매겨져 있어, 바로 앞번호의 학생이나 바로 뒷번호의 학생에게만 체육복을 빌려줄 수 있습니다.
• 예를 들어, 4번 학생은 3번 학생이나 5번 학생에게만 체육복을 빌려줄 수 있습니다. 체육복이 없으면 수업을 들을 수 없기 때문에 체육복을 적절히 빌려 최대한 많은 학생이 체육수업을 들어야 합니다.
• 전체 학생의 수 n, 체육복을 도난당한 학생들의 번호가 담긴 배열 lost, 여벌의 체육복을 가져온 학생들의 번호가 담긴 배열 reserve가 매개변수로 주어질 때, 체육수업을 들을 수 있는 학생의 최댓값을 return 하도록 solution 함수를 작성해주세요.

❗제한 조건

---

• 전체 학생의 수는 2명 이상 30명 이하입니다.
• 체육복을 도난당한 학생의 수는 1명 이상 n명 이하이고 중복되는 번호는 없습니다.
• 여벌의 체육복을 가져온 학생의 수는 1명 이상 n명 이하이고 중복되는 번호는 없습니다.
• 여벌 체육복이 있는 학생만 다른 학생에게 체육복을 빌려줄 수 있습니다.
• 여벌 체육복을 가져온 학생이 체육복을 도난당했을 수 있습니다. 이때 이 학생은 체육복을 하나만 도난당했다고 가정하며, 남은 체육복이 하나이기에 다른 학생에게는 체육복을 빌려줄 수 없습니다.

📌 풀이

---

1. 최적해를 찾는 문제이므로 탐욕법(Greedy Algorithm)을 사용할 수 있다.
2. 인접한 번호에만 빌려줄 수 있으므로 빌려줄 학생들을 "정해진 순서" 로 살펴야 하고, 이 "정해진 순서"에 따라 우선하여 빌려줄 방향을 정해야함.

방법1 (전체 학생 수 n이 작은경우)

• 학생 수 만큼 배열을 확보하고, 여기에 각자가 가지고 있는 체육복의 수를 기록한다.
• 번호 순서대로 "스캔"하면서 빌려줄 관계를 정한다.
• 복잡도는 O(n)

def solution(n, lost, reserve):
	# 계산의 처리를 쉽게하기 위해 배열의 앞과 끝에 더미 데이터 추가
    u = [1] * (n+2)
    
    # 학생들의 가지고 있는 체육복 개수를 입력 갱신
    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]
        elif u[i] == 2 and u[i+1] == 0:
        	u[i:i+2] = [1,1]
    
    return len([x for x in u[1:-1] if x > 0])

방법2 (전체 학생 수 n은 매우 큰데, 여벌의 체육복 k는 매우 적은 경우)

• 여벌의 체육복을 가져온 학생들의 번호(reserve)를 정렬하고, 이것을 하나 하나 순서대로 살펴보면서 빌려줄 수 있는 다른 학생을 찾아서 처리.
• 정렬에 O(klog k), 다른 학생을 찾는 알고리즘에 해시를 적용해서 상수 시간에 처리가능
• 전체 복잡도는 O(klog k)

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)