[Python 프로그래머스] 체육복 - 초보를 위한 자세한 설명 | 탐욕법 | 그리디 알고리즘

탐욕법 문제입니다.

탐욕 알고리즘(탐욕법, Greedy Algorithm)은 최적해를 구하는 데에 사용되는 근사적인 방법으로, 여러 경우 중 하나를 결정해야 할 때마다 그 순간에 최적이라고 생각되는 것을 선택해 나가는 방식으로 진행하여 최종적인 해답에 도달한다.
-출처: 위키백과-

---

문제 설명

점심시간에 도둑이 들어, 일부 학생이 체육복을 도난당했습니다. 다행히 여벌 체육복이 있는 학생이 이들에게 체육복을 빌려주려 합니다. 학생들의 번호는 체격 순으로 매겨져 있어, 바로 앞번호의 학생이나 바로 뒷번호의 학생에게만 체육복을 빌려줄 수 있습니다. 예를 들어, 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 = n - len(lost)    # 전체학생에서 체육복 도둑맞은 학생 수업가능 인원에서 빼기
    
    for i in range(len(lost)):    # 먼저 lost 와 reserve 에 중복되는 사람을 제거하기 위한 루프
        for j in range(len(reserve)):
            if reserve[j] == lost[i]:
                answer += 1    # 중복되는 사람들은 수업 가능이니 다시 더하기
                reserve[j] = -1
                lost[i] = -1    # 다음루프에 중복제거를 위해 해당번호들은 -1 로 변경
                break
                
    for i in range(len(lost)):    # 체육복을 빌릴 앞뒤 사람을 찾을 루프
        for j in range(len(reserve)):
            if reserve[j] - 1 == lost[i]:    # 체육복 도둑맞은 사람의 전 번호 찾기
                answer += 1    # 찾으면 수업가능인원 +1
                reserve[j] = -1     # 다음루프에 중복제거를 위해 해당번호들은 -1 로 변경
                break
            elif reserve[j] + 1 == lost[i]:    # 전 번호가 없을시 후 번호
                answer += 1
                reserve[j] = -1
                break
    return answer

일단 답은 어렵지 않게 구했는데, 시간복잡도를 어떻게 줄일 수 있는지 모르겠네요..

---

가장 빠른 속도가 나오는 다른 사람의 풀이

def solution(n, lost, reserve):

    reserve = set(reserve)    # reserve 를 집합으로 바꾼다.

    for size in [0, 1, -2]:   
        lost = set(map(lambda x : x+size, lost))
        reserve, lost = reserve - lost, lost - reserve                         
	# for문 첫 번째는 lost = reserve를 제거, 
 	# 두 번째는 lost + 1 = reserve를 제거,
 	# 세 번째는 lost - 1 = reserve를 제거하는 구문
    return n - len(lost)

 

기타 문법 설명

• set 함수
  - set은 수학에서 이야기하는 집합과 비슷합니다.
  - 순서가 없고, 집합 안에서는 unique한 값을 가집니다.(중복이 없음)
  - 중괄호를 사용하는 것은 dictionary와 비슷하지만, key가 없습니다. 값만 존재합니다.
  

  >>> s = set([1,1,3,3,5,7])
  >>> s
  {1, 3, 5, 7}
  >>> p = {1, 3, 5, 7}
  >>> p
  {1, 3, 5, 7}

  
  

• map 과 lambda 함수
  - map(함수, 리스트)
  - lambda 인자 : 표현식

  >>> ls = ['1','2','3']
  >>> list(map(int, ls))
  >>> [1, 2, 3]
  
  >>> set(map(lambda x: x ** 2, range(5)))
  >>> {0, 1, 4, 9, 16}

---

짧은 후기

제가 작성한 건 1차원적인 방법인 거 같아요. 다른 분이 작성한 건 굉장히 간결하고 깔끔하네요. 어떻게 저런 코드를 쓰는지 대단합니다.