3. 체육복

1) 문제

(1) 문제 정보

• 탐욕법

• LEVEL1

• 문제보러가기

  
  

(2) 문제 설명

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

2) 풀이

이 문제는 그리디 문제입니다.

(0) 문제 해결 시 놓친 점

일반복사

a = [1, 2, 3, 4]
b = a       # shallow copy
print(b)    # [1, 2, 3, 4]
b[2] = 100   # b의 item 변경
print(b)    # [1, 2, 100, 4]
print(a)    # [1, 2, 100, 4], a의 item도 수정됨

얕은 복사

• shallow copy로 복사된 리스트는 별도의 객체이므로 item을 수정하면 복사본만 수정된다.(요소가 immutable 하기 때문)

• immutable 하다는 것은, 요소가 수정되는 것이 아니라 그저 다른 값으로 대체된다는 것이다.

• 그러므로 b에서 변경된 요소가 a 에는 반영되지 않는다.(두 리스트는 다른 객체이므로..)

import copy

a = [1, [1, 2, 3]]
b = copy.copy(a)    # shallow copy 발생
print(b)            # [1, [1, 2, 3]] 출력
b[0] = 100
print(b)            # [100, [1, 2, 3]] 출력
print(a)            # [1, [1, 2, 3]] 출력

• 아래가 둘 다 수정된 건, 리스트 item 내부 객체가 동일한 객체이므로 mutable한 리스트를 수정할 때는 둘다 변경된다.

c = copy.copy(a)
c[1].append(4)     # 리스트의 두번째 item(내부리스트)에 4를 추가
print(c)           # [1, [1, 2, 3, 4]] 출력
print(a)           # [1, [1, 2, 3, 4]] 출력

깊은 복사

import copy

a = [1, [1, 2, 3]]
b = copy.deepcopy(a)    # deep copy 실행
print(b)                # [1, [1, 2, 3]] 출력
b[0] = 100
b[1].append(4)
print(b)                # [100, [1, 2, 3, 4]] 출력
print(a)                # [1, [1, 2, 3]] 출력

정확성	연산시간	메모리
100%	0.01 ~ 0.03ms	10 ~ 10.3MB

a. lost == reserve인 원소를 삭제한다.(여분을 가진 사람이 하나를 도난 당한 경우)

b. 먼저 빌리는 사람이 앞사람에게 빌리면, 뒷사람이 빌릴 수 있는 확률이 높기에 i-1을 먼저 탐색한다.

c. 결과값은 n에서 빌리지 못한 사람만 빼면 된다.

def solution(n, lost, reserve):
    # a
    removed = []
    for i in lost:
        for j in reserve:
            if (i == j):
                removed.append(i)
    for a in removed:
        lost.remove(a)
        reserve.remove(a)
    
    # b
    for i in reserve:
        if (i-1) in lost:
            lost.remove(i-1)
        elif (i+1) in lost:
            lost.remove(i+1)
    
    # c
    return n- len(lost)