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

참고: https://school.programmers.co.kr/learn/courses/30/lessons/42862

 

✔️ 문제

 

 

문제는 다음과 같다.

 

 

✔️ 풀이

 

 

그림이 조금 못생겼지만, 다음과 같이 설명할 수 있다.

 

1) 2번과 4번 학생이 체육복을 잃어버렸지만, 1에 인접한 2에게 체육복을 주고,

3에 인접한 2와 4에게 체육복을 주고, 5에 인접한 4에게 체육복을 줌으로써

총 5명이 체육수업을 들을 수 있다.

2) 2번과 4번 학생이 체육복을 잃어버렸지만, 3에 인접한 2와 4에게 체육복을 줌으로써

총 5명이 체육수업을 들을 수 있다.

3) 3번 학생이 체육복을 잃어버렸는데, 3에 인접한 수가 없기 때문에

총 2명이 체육수업을 들을 수 있다.

 

이 외에도 여러가지 반례를 생각해보았다.

 

1) n이 5이고 lost가 [1,2,3] 이고 reserve가 [2,4,5] 라면,

2번 학생은 여벌이 있으면서 체육복을 잃어버렸기 때문에 본인의 체육복밖에 없다.

그래서 lost는 [1,3]으로, reserve는 [4,5]로 생각할 수 있다.

2번 학생은 더이상 줄 수 없지만 4번에 인접한 3번 학생에게 체육복을 줄 수 있고,

5번에 인접한 학생은 더이상 없기 때문에 총 4명이 체육수업을 들을 수 있다.

2) n이 2이고 lost가 [2] 이고 reserve가 [1] 라면,

1번 학생의 여벌을 2번 학생에게 줌으로써

총 2명이 체육수업을 들을 수 있다.

 

이렇게 반례를 생각해본 이유가 처음에 코드를 작성할 때,

기존 student의 학생 번호의 max값을 넘지 않는 선에서 +1만큼을 주고

0보다 작지 않은 선에서 -1만큼을 준다음에 길이를 return 하였다.

이렇게 하니까 테스트케이스 3번과 4번만 틀린 경우가 되었다.

 

그래서 다시 생각해보고, 이것저것 찾아보면서

set을 활용하여 새롭게 만든 각각의 원소를 -1과 +1한 만큼이 있다면,

제거하고 n에서 해당 잃어버린 학생의 수를 빼는 과정이

제일 탐욕적이고 그리디적인 알고리즘을 찾게 되었다.

 

def solution(n, lost, reserve):
    new_reserve = set(reserve) - set(lost)
    new_lost = set(lost) - set(reserve)
    for i in new_reserve:
        if i-1 in new_lost:
            new_lost.remove(i-1)
        elif i+1 in new_lost:
            new_lost.remove(i+1)
    
    return n-(len(new_lost))

 

집합과 집합의 차는 차집합을 만들 수 있는데,

반례 1번처럼 겹치는 학생은 결국 본인의 체육복만 입을 수 있으므로

잃어버린 학생과 여벌의 학생을 각각의 차집합으로 따로 전처리를 시켜준다.

 

그 다음, 여벌의 학생의 원소를 돌면서

해당 원소보다 -1만큼 작은 원소가 잃어버린 학생에 있다면 제거하고

+1만큼 큰 원소가 잃어버린 학생에 있다면 또 제거한다.

 

예제 1번처럼 결국 1보다 큰 2가 new_lost에 있으므로 제거하고,

3보다 큰 4가 new_lost에 있으므로 제거하게 되면,

여벌을 다 나누어준 결과가 되기 때문에 전체 학생 수에서 new_lost의

길이만큼을 뺀 결과가 정답이 되는 것이다.

 

화이팅 💪