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

- 문제 설명

점심시간에 도둑이 들어, 일부 학생이 체육복을 도난당했습니다. 다행히 여벌 체육복이 있는 학생이 이들에게 체육복을 빌려주려 합니다. 학생들의 번호는 체격 순으로 매겨져 있어, 바로 앞번호의 학생이나 바로 뒷번호의 학생에게만 체육복을 빌려줄 수 있습니다. 예를 들어, 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명이 체육수업을 들을 수 있습니다.

---

 이번 문제는 지문부터 참 길다보니 풀기 꺼려지는 문제였습니다. 하지만 프로그래머스는 입출력 예시에 대한 자세한 설명이 있어 빠르게 이해하는데 도움이 되어서 참 좋은 것 같습니다. 이 문제는 Greedy Algorithm을 사용하여 풀도록 문제 범주가 정해져있는데 Greedy Algorithm은 항상 최적해를 보장해주지는 않지만 대부분의 경우 최적해를 찾기에 적합한 알고리즘이기도 합니다. Greedy Algorithm에 대해 궁금하시다면 다음 포스팅 글을 참고해주시기 바랍니다. 

DP와 Greedy Algorithm

 알고리즘 문제에는 제한사항에 답이 있다고 할 정도로 제한사항에는 많은 힌트들이 숨어있습니다. 또한 제한사항들을 보고 예외처리를 해주어야 통과할 수 있는 문제도 있으며(e.g Divide Zero) 주어진 조건의 return 값이 0~1000까지로 정해져있어 연산 횟수를 줄일 수 있는 조건이 되기도 합니다. 

 제가 이번 문제의 제한 사항에서 유심히 본 내용은 "중복이 없다" 와 "여별의 체육복이 있는 학생도 도난 당했을 수 있다" 입니다. 알고리즘에 대한 지식이나 이를 다룰 줄 아는 기술도 중요하지만 정작 문제를 제대로 이해하지 못한다면 아무짝에 쓸모 없습니다.. 이런 면에서 저 말을 어떻게 잘 이해하느냐에 따라 이 문제를 풀 수 있냐 없냐가 갈렸던 것 같습니다.

 "중복이 없다" 라는 것은 Lost 와 Reserve 내의 원소값이 unique하다는 것입니다. 즉, lost =[1,1,2] reserve=[3,3,5,4,2] 가 될 수 없습니다. 

 "여별의 체육복이 있는 학생(reserve)도 도난 당했을 수 있다" 라는 것은 lost값에 reserve값이 공통적으로 존재할 수 있다라는 것을 의미합니다. 예를 들면, lost=[1,2,3] , reserve[3,4,5] 처럼 말이죠. 이때 여벌의 체육복은 1개밖에 없다고 가정하므로 reserve에 있는 3은 체육복을 빌려줄 수 없습니다.  따라서 lost와 reserve에 같은 값이 있다면 그 값은 reserve에서 제외시켜주어야 합니다.

 

여기까지 이해되셨다면 문제는 모두 푼 것이나 마찬가지입니다. 저는 먼저 "여벌의 체육복이 있는 학생도 도난 당했을 수 있다" 라는 전처리(Preprocessing)을 해주었습니다. 왜냐하면 반복문을 통해 전체 값을 도출해낼때 애초에 Reserve값이 잘못되어있다면 틀린 값이 나오기 때문이죠.

따라서 Reserve의 요소들 중 Lost에 동일하게 존재하는 값들은 모두 제거해주어야 합니다.

set_reserve=set(reserve)-set(lost)
set_lost = set(lost)-set(reserve)

set 자료형은 중복을 허용하지 않는 집합 자료형입니다. set의 장점이라면 객체 끼리 집합 연산을 지원한다는 것인데, 다음과 같이 '-' 기호를 이용해 각 집합별로 차집합을 수행할 수 있습니다. 참고로 list 자료형은 '-' 와 같은 차집합 연산이 지원되지 않습니다. 제한 조건 중 중복을 허용하지 않는다는 lost 와 reserve이기 때문에 set자료형을 쓴다고해서 lost와 reserve값에 어떠한 변화는 없습니다. 

(c.f 중복이 있는 list 끼리 차집합 연산을 수행하기 위해서는 Counter 객체를 사용하시면 됩니다. 궁금하시다면 구글에 검색..)

위와 같은 전처리를 해준다면 set_reserve와 set_lost 의 비교 준비가 끝난 것입니다.

입출력 예시 1

이제 입출력 예시 1번을 예로 들어 Greedy Algorithm을 해보겠습니다. 

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

5명의 학생이 있다고 했을 때 체육복을 잃어버린 2,4번 학생은 각각 1,3번 3,5번 학생으로 부터 체육복을 빌려받을 수 있습니다. 그렇다면 reserve를 기준으로 왼쪽에 있는 학생부터 빌려주는것이 맞을까요 아니면 오른쪽에 있는 학생부터 빌려주는 것이 맞을까요? 

변형 예

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

다음과 같이 예시를 변형해보겠습니다. reserve에서 1이 빠진 예시인데요. 4번 학생은 3번과 5번 학생으로부터 모두 체육복을 받을 수 있습니다. 만약에 체육복을 빌려주는 방향을 reserve 요소를 기준으로 오른쪽에 있는 값을 먼저 빌려준다면 어떻게 될까요?

reserve 3을 기준으로 4번 학생은 체육복을 빌려서 체육 시간에 참가할 수 있을 것입니다. 하지만 2번학생은 3번 학생으로 부터 체육복을 받을 수 있음에도 받지 못하며, 4번학생은 3번이 빌려주지 않아도 5번으로 받을 수가 있었습니다. 

이런 예시로 볼 때 체육복을 양 옆 학생에게 빌려줄 수 있다면 왼쪽 요소부터 탐색해야함을 알 수 있습니다.

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

따라서, reserve의 i-1 요소 즉, reserve학생의 왼쪽 학생부터 빌려주고 만약에 없다면 오른쪽 학생을 주는 식으로 알고리즘을 작성해야합니다.

 

탐욕법 알고리즘을 사용해 reserve의 요소마다 local optimum인 왼쪽 요소부터 탐색하여 전체 최적의 해를 찾는 문제였습니다.