[프로그래머스] 체육복 - 그리디 greedy (python)

1. 문제 설명

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

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

 

즉, 체육복을 잃어버린 학생, 여벌옷을 가지고 있는 학생, 전체 학생수가 주어질 때 수업을 들을 수 있는 최대 학생의 수를 구해야 한다.

---

2. 제한 사항

• 전체 학생의 수는 2명 이상 30명 이하입니다.
• 체육복을 도난당한 학생의 수는 1명 이상 n명 이하이고 중복되는 번호는 없습니다.
• 여벌의 체육복을 가져온 학생의 수는 1명 이상 n명 이하이고 중복되는 번호는 없습니다.
• 여벌 체육복이 있는 학생만 다른 학생에게 체육복을 빌려줄 수 있습니다.
• 여벌 체육복을 가져온 학생이 체육복을 도난당했을 수 있습니다. 이때 이 학생은 체육복을 하나만 도난당했다고 가정하며, 남은 체육복이 하나이기에 다른 학생에게는 체육복을 빌려줄 수 없습니다. ∴ 리스트에 중복 값이 있을 경우 제거하고 시작해야한다.

---

3. 입출력 예

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

 

---

4. 나의 풀이

이 문제 또한 예전에 풀었기 때문에 혹시나 하는 마음에 지우고 다시 풀어보았다. 그 결과...

def solution(n, lost, reserve):

    for res in reserve:
        if res in lost:
            lost.remove(res)
            reserve.remove(res)
    answer = n - len(lost)
    for i in lost:
        if i in reserve:
            answer += 1
            reserve.remove(i)
        elif i - 1 in reserve:
            answer += 1
            reserve.remove(i - 1)
        elif i + 1 in reserve:
            answer += 1
            reserve.remove(i + 1)

    return answer

예전 풀이

def solution(n, lost, reserve):
    reserve_n = list(set(reserve) - set(lost))
    lost_n = list(set(lost) - set(reserve))
    
    answer = n - len(lost_n)
    for i in lost_n:
        if i - 1 in reserve_n:
            answer += 1
            reserve_n.remove(i - 1)
        elif i + 1 in reserve_n:
            answer += 1
            reserve_n.remove(i + 1)
    
    return answer

오늘 풀이

 

윗 부분 세 줄을 제외하고 거의 똑같이 풀었다 ! ! ! ! !!! 그나마 elif 문 하나가 줄은거..? 조금이라도 발전했을줄 알았는데 거기서 거기였다. 쉬운 문제라서 그런거라 스스로 위로중이다..

우선, 체육복을 잃어버린 애들 중, 여벌옷이 있는 애들은 고려하지 않아야 한다. 따라서 set을 이용하여 중복을 제거한다.

python에서 set은 집합 자료형을 의미하는데, 1. 중복을 허용하지 않는다. 2. 순서가 없다. 는 특징을 가지고 있다. 여기서는 1번의 특징을 이용하여 중복을 제거하였다. 또한, set은 원소끼리 빼기가 가능하기 때문에 중복을 제거하기에 용이하다.

 

그러나! 리스트 자체에 중복 원소가 가진 의미가 큰 경우는 set을 써도 의미가 없다. 예를 들어, a = [1, 2, 3, 4, 4, 5] 와 b = [2, 4, 5]의 리스트가 있을 때, 직관적으로 a 원소 중 b와 겹치는 원소를 제거한 [1, 3, 4]가 필요한 경우에 set으로 제거를 하면 [1, 3]이 나오게 된다. 이미 set(a)하는 과정에서 4가 중복되어 하나가 제거되기 때문이다.

set으로 중복 제거가 불가능한 경우

그 다음, answer에 이미 체육복을 가진 학생의 수인 n - len(lost_n)를 넣고, lost_n을 순회하며 reserve_n에 앞순서, 뒷순서에 체육복을 가지고 있는 학생이 있으면 reserve_n에서 삭제하고 answer에 1을 늘린다.

이때, 그리디 알고리즘을 조금 생각하면서 풀기도 했다. 그리디 알고리즘이란, 최적해를 구하는 데에 사용되는 근사적인 방법으로, 여러 경우 중 하나를 결정해야 할 때마다 그 순간에 최적이라고 생각되는 것을 선택해 나가는 방식으로 진행하여 최종적인 해답에 도달하는 알고리즘이다. lost_n의 원소 하나하나를 보면서, reserve_n에 가능한 대체재가 존재하면 바로 가져다 쓰는 방법을 이용했다.

해당 풀이의 경우 for문으로 O(n), remove에서 O(n)으로 시간 복잡도가 O(n^2)에 달한다. 효율적이진 않지만 ,, 다른 방법을 조금 더 생각해보아야겠다.

 

문제 링크: https://programmers.co.kr/learn/courses/30/lessons/42862

 

코딩테스트 연습 - 체육복

 

 

 

 

그리디 알고리즘은 그때그때 가장 최적의 해를 고르는 것이기 때문에 전역적인 해를 골랐다고 해서 그것이 가장 최적인 해라는 보장은 없다.

출처 : https://ko.wikipedia.org/wiki/%ED%83%90%EC%9A%95_%EC%95%8C%EA%B3%A0%EB%A6%AC%EC%A6%98