탐욕법(Greedy)

탐욕법(Greedy)은 '탐욕'이라는 말 그대로 현 상황에서 당장 좋은 것만 고르는 방법이다.

사실 이론적으로는 이해하기 쉽지만, 막상 문제를 풀라하면 모르겠다.

 

프로그래머스 체육복 문제를 풀어보자. 문제는 다음과 같다.

 

문제 설명
점심시간에 도둑이 들어, 일부 학생이 체육복을 도난당했습니다. 다행히 여벌 체육복이 있는 학생이 이들에게 체육복을 빌려주려 합니다. 학생들의 번호는 체격 순으로 매겨져 있어, 바로 앞번호의 학생이나 바로 뒷번호의 학생에게만 체육복을 빌려줄 수 있습니다. 예를 들어, 4번 학생은 3번 학생이나 5번 학생에게만 체육복을 빌려줄 수 있습니다. 체육복이 없으면 수업을 들을 수 없기 때문에 체육복을 적절히 빌려 최대한 많은 학생이 체육수업을 들어야 합니다.

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

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

입출력 예

n	lost	reserve	return
5	[2, 4]	[1, 3, 5]	5
5	[2, 4]	[3]	4
3	[3]	[1]	2

 

입출력 예 설명
예제 #1
1번 학생이 2번 학생에게 체육복을 빌려주고, 3번 학생이나 5번 학생이 4번 학생에게 체육복을 빌려주면 학생 5명이 체육수업을 들을 수 있습니다.

예제 #2
3번 학생이 2번 학생이나 4번 학생에게 체육복을 빌려주면 학생 4명이 체육수업을 들을 수 있습니다.

 

여기에서 유의해야할 부분은 빨간색으로 마킹한 문장이다. 처음에 저 것을 생각안하고 풀었다가 통과하지 못했다.

 

def solution(n, lost, reserve):
    answer = 0
    
    #여벌이 있는 학생이 도난당했을 수도 있으니 이 학생을 제외하기 위해 변수로 저장
    stolen = set(lost) & set(reserve)
    
    #stolen을 제외한 lost와 reserve 리스트를 정렬
    #set을 이용하였기 때문에 다시 정렬한 후 for문을 돌려야 서로 비교가 가능
    lost = sorted(list(filter(lambda x : x not in stolen, lost)))
    reserve = sorted(list(filter(lambda x : x not in stolen, reserve)))
    
    #filter 함수는 어떤 기준에 따라 원하는 데이터만 선택하여 추출할 수 있어, stolen을 제외한 데이터만 정렬하기 위해 사용하였다.
    
    #lost 리스트로 빌려 수 있는 학생을 추출하기 위해 for문을 돌린다. 앞 -1 뒤 +1을 이용하여 추출
    #lost에서 추출해낸 빌려 수 있는 학생과 reserve 값과 비교하기 위해 if문을 이용 
    #비교하였을 때 lost에서 추출해낸 값이 reserve에 없다면 빌릴 수 없는 학생이니 총 학생수(n)에서 -1만큼 해줘 빌릴 수 있는 학생 수만 return 한다.
    for i in lost:
        if i - 1 in reserve:
            reserve.remove(i-1)
        elif i + 1 in reserve:
            reserve.remove(i+1)
        
        else:
            n -= 1
        
    return n

 

이 문제가 탐욕법(Greedy) 와 어떤 연관이 있는건지 고민해보았다.

 

탐욕법은 앞서 말했듯이 현 상황에서 당장 좋은 것만 고르는 방법이다.

lost리스트로 for문을 돌렸을 때 그 다음 학생이 체육복을 빌릴 수 있든지 없든지 간에 현 학생이 빌릴 수 있다면 그만이다.

따라서 remove를 이용해 빌릴 수 있는 학생을 한명씩 제거해 나가는 방법으로 코드를 작성하였다.

 

그리고 문제에서 체육수업을 들을 수 있는 학생의 최댓값을 return하라고 하였다.

이 말은 최대한 많은 학생들이 체육수업을 들을 수 있게 하라라는 말로 바꿔 이해하였다.

만약, 체육복이 없는 학생이 빌릴 수 있는 상황에서도 빌리지 않고 다음 학생한테 양보한다고 가정하였을 때, 다음 학생은 굳이 양보받지 않아도 뒷 번호 학생에게 빌릴 수 있는 상황이 올 수 있으니 이렇게 된다면 최댓값을 도출할 수 없다.

 

그러니 빌릴 수 있는 상황이라면 무조건 빌려야 하는 것이 해당 조건을 만족시킬 수 있으며 이는 탐욕법(Greedy)에 해당한다.