02 체육복 - Greedy

문제 설명

도둑 들어서 일부 학생이 체육복을 도난 당함, 여벌이 있는 학생이 있어 이들에게 체육복을 빌려주려함

학생들의 번호는 체격 순으로 매겨져 있어, 바로 앞이나 뒷번호의 학생에게만 빌려줄 수 있음

체육복이 없으면 수업을 못듣기 때문에 최대한 많은 학생이 체육수업을 들어야함

 

전체 학생의 수 n, 체육복을 도난 당한 학생들의 번호가 담긴 배열 lost, 여벌의 체육복을 가져온 학생들의 번호가 담긴 배열 reserve가 매개변수로 주어질 때, 체육 수업을 들을 수 있는 학생의 최댓값을 return 하도록 solution 함수를 작성

 

제한 사항

- 전체 학생의 수는 2명 이상 30명 이하

- 체육복을 도난 당한 학생의 수는 2명이상 n명 이하이고 중복되는 번호는 없음

- 여벌의 체육복을 가져온 학생의 수는 1명 이상 n명 이하이고 중복되는 번호는 없음

- 여벌 체육복이 있는 학생만 다른 학생에게 체육복을 빌려줄 수 있음

- 여벌 체육복을 가져온 학생이 체육복을 도난 당할 수 있음, 이때 이 학생은 체육복을 하나만 도난당했다고 가정, 남은 체육복이 하나이기에 다른 학생에게는 체육복을 빌려줄 수 없음 

 

---

1차 시도

def solution(n, lost, reserve):     # 전체 학생 수, 도난당한 학생들의 번호 배열, 여벌의 체육복을 가져온 학생들의 번호 배열 
    answer = 0      # 체육 수업을 들을 수 있는 학생의 최댓값

    #answer = n - len(lost)      # 아무에게도 못 빌려줬을 경우 체육수업을 들을 수 있는 학생 수
    count = [0] * (n + 1)        # 학생 별 가지고 있는 체육복 수 

    for i in range(1, n + 1):
        if i not in lost:  # 도난 당하지 않은 사람 체육복 갯수 + 1
            count[i] += 1
        if i in reserve:   # 여벌의 체육복 있는 사람 체육복 갯수 + 1
            count[i] += 1

    for i in range(1, n + 1):
        if count[i] < 2:
            continue

        pre_student = 0     # 앞번호 학생
        next_student = 0    # 뒷번호 학생

        if i == 1 :
            pre_student = 0
            next_student = i + 1
        elif i == n:
            pre_student = i - 1
            next_student = 0
        else :
            pre_student = i - 1   # 여벌 체육복 있는 학생의 앞 번호
            next_student = i + 1  # 여벌 체육복 있는 학생의 뒷번호
        
        for j in lost:
            if (pre_student == j or next_student == j) and count[j] == 0:  # 앞, 뒤 학생 중 한명이고, 빌린 체육복이 없다면
                count[i] -= 1
                count[j] = 1
                break
    answer = 0
    for i in range(1, n + 1):
        if count[i] > 0:
            answer += 1

    return answer

2차 시도

def solution(n, lost, reserve):     # 전체 학생 수, 도난당한 학생들의 번호 배열, 여벌의 체육복을 가져온 학생들의 번호 배열 
    answer = 0      # 체육 수업을 들을 수 있는 학생의 최댓값

    #answer = n - len(lost)      # 아무에게도 못 빌려줬을 경우 체육수업을 들을 수 있는 학생 수
    count = [0] * (n + 1)        # 학생 별 가지고 있는 체육복 수 
    lost.sort()
    reserve.sort()

    for i in range(1, n + 1):
        if i not in lost:  # 도난 당하지 않은 사람 체육복 갯수 + 1
            count[i] += 1
        if i in reserve:   # 여벌의 체육복 있는 사람 체육복 갯수 + 1
            count[i] += 1

    for i in range(1, n + 1):
        if count[i] < 2:    # 빌려줄 체육복이 없는 경우
            continue

        pre_student = 0     # 앞번호 학생
        next_student = 0    # 뒷번호 학생

        if i == n:
            pre_student = i - 1
            next_student = 0
        else :
            pre_student = i - 1   # 여벌 체육복 있는 학생의 앞 번호
            next_student = i + 1  # 여벌 체육복 있는 학생의 뒷번호
        
        for j in lost:
            if (pre_student == j or next_student == j) and count[j] == 0:  # 앞, 뒤 학생 중 한명이고, 빌린 체육복이 없다면
                count[i] -= 1
                count[j] = 1
                break
    answer = 0
    for i in range(1, n + 1):
        if count[i] > 0:
            answer += 1

    return answer

- 처리하기 전 lost와 reserve 배열을 각각 정렬하고 알고리즘을 수행했더니 정확성 테스트를 통과했다.

개선점

 

---

바람직한 풀이

 

탐욕법 : 알고리즘의 각 단계에서 그 순간에 최적이라고 생각되는 것을 선택 

✔ 현재의 선택이 마지막 해답의 최적성을 해치지 않을때 

 

- 빌려줄 학생들을 '정해진 순서'로 살펴야하고, 정해진 순서에 따라 우선하여 빌려줄 방향을 정해야함

 

방법 1  : 학생의 수는 기껏해야 30! 

- 학생 수 만큼 배열 확보, 각자가 가지고 있는 체육복 수 확인

1. 학생 수 만큼의 배열 : Default - 체육복 1개, 여벌 있는 경우 +1. 잃어버린 학생의 경우 -1.

2. 1번 부터 탐색해서 앞,뒤의 학생에게 빌려줄 수 있는지 체크

: 앞뒤 학생이 체육복 있으면 빌려주지 않는다, 없으면 빌려줌

3. 체육복 있는 학생의 수 Count (갯수 > 0)

== 내가 푼 방식과 동일하다

-> 복잡도 : O(n)

 

🙄 전체 학생 수가 크고, 여벌의 체육복을 가진 학생이 적은데 모든 배열을 탐색?

 

방법 2 : 여벌의 체육복 있는 학생들의 번호(reserve) 정렬, 빌려줄 수 있는 다른 학생을 찾아서 처리

- 복잡도 = 정렬의 복잡도 O(klogk) : 학생의 수가 적을 경우엔 방법 1이 유리

- 해시를 적용하여 상수시간에 처리!

 

1. lost와 reserve에 둘다 있는 번호 삭제

2. reserve를 하나씩 탐색하며 lost에 빌려 줄 사람이 있는지 체크, 빌려줄수있는 번호는 lost 배열에서 삭제

3. 체육복이 있는 학생 수 = 전체학생수 - lost에 남은 학생 수

 

코드 구현

- 방법 1

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]	# 둘다 1로 만들음
        elif u[i + 1] == 0 and u[i] == 2: # 뒤의 학생이 체육복이 없는 경우
        	u[i : i + 2] = [1, 1]	# 뒤의 학생에게 빌려줌 : 둘다 갯수 1
    
    # 체육 수업에 참여할 수 있는 학생의 수        
	return len([x for x in u[1:-1] if x > 0])	# 체육복 보유 수가 0보다 큰 학생의 수

- 방법 2

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)	# 체육복 빌려줌 : l 집합에서 제거
        elif x + 1 in l :	# 뒤의 학생이 체육복이 없는 학생일 경우 체육복 빌려줌
        	l.remove(x + 1)	
    return n - len(l)	# 수업을 들을 수 있는 학생 = 전체 학생 - 빌리지 못한 학생의 수

- 집합을 사용하여 교집합, 차집합을 사용하는 방법