[프로그래머스] 체육복 (탐욕법 Greedy)

문제 url: https://school.programmers.co.kr/learn/courses/30/lessons/42862

프로그래머스

---

def solution(n, lost, reserve):
	# 오름차순으로 정렬
    lost.sort()
    reserve.sort()
    
    # 차집합을 이용해 여벌옷이 있는데 도난당했을 경우 제외
    new_lost = set(lost) - set(reserve)
    new_reserve = set(reserve) - set(lost)
    
    for r in new_reserve:
        if r - 1 in new_lost:
            new_lost.remove(r-1)
        elif r + 1 in new_lost:
            new_lost.remove(r+1)
    return n - (len(new_lost))

set 함수는 수학에서의 집합과 비슷하며 중복을 제거해준다. 

문제를 보면, lost(도난 당한 학생 번호 리스트), reserve(여벌 체육복 있는 학생 번호 리스트)를 나타낸다.

sort함수를 이용해 오름차순으로 정렬해 준 뒤, 

set함수를 이용하여 차집합 연산을 수행해 여벌 체육복이 있는 학생이 도난 당했을 경우를 제외한다.

 

lost에 있는 값에서 +1, -1 인 번호만 체육복을 빌려줄 수 있으므로 reserve에 있는 값 + 1, reserve에 있는 값 -1 의 번호가 lost에 있다면 해당 번호를 제거해준다.

이때, reserve 번호 왼쪽에 있는(1 작은) lost 학생에게 빌려주는 것을 우선으로 둔다.

Ex) lost [2,4] reserve[3,5]

      3번이 4번에게 빌려주면 2번은 5번에게 빌려입지 못하므로 체육수업을 들을 수 없기 때문이다.

그리고 전체 학생 수에서 new_lost 길이(도난당한 학생 수)를 빼주면 체육수업을 들을 수 있는 학생 수가 나온다.

---

풀이 참고 url: https://rain-bow.tistory.com/30

[Python] 프로그래머스 - 체육복

 

어김없이 구글링... 언제쯤 혼자 할 수 있을까😥