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

난이도 : level 1
유형 : 그리디
출처 : https://school.programmers.co.kr/learn/courses/30/lessons/42862

---

문제 요약

• 전체 학생 수 n
• 체육복을 도난당한 학생들의 번호 배열 lost
• 여벌 체육복이 있는 학생들의 번호 배열 reserve

학생들은 바로 앞번호나 뒷번호 학생에게만 체육복을 빌려줄 수 있다.
최대한 많은 학생이 수업을 들을 수 있도록 했을 때, 수업 가능한 학생의 최댓값을 구하라.

1. 학생 번호를 정렬해서 앞뒤 확인을 쉽게 한다.

2. 여벌 체육복이 있지만 동시에 도난당한 학생은 자기 것만 입으면 되므로
   lost와 reserve에서 제거한다.

3. 여벌이 있는 학생을 순회하면서

   • 먼저 앞번호 학생에게 빌려줄 수 있는지 확인
   • 불가능하면 뒷번호 학생에게 빌려준다.

4. 전체 학생 수 n에서 아직 체육복이 없는 lost의 길이를 빼면 된다.

해답 및 풀이

# n: 도난 당한 학생 수, lost: 그 학생들의 번호 배열, reserve: 체육복을 있는 학생 수 배열
def solution(n, lost, reserve):
    # 정렬
    lost.sort()
    reserve.sort()
	
    # lost, reserve에 공통으로 있는 요소 제거
    for i in reserve[:]: # [:]는 밑에서 설명
        if i in lost:
            reserve.remove(i)
            lost.remove(i)
	
    # 체육복 빌려주기(나의 앞 번호부터 확인)
    for i in reserve:
        if i-1 in lost:
            lost.remove(i-1)
        elif i+1 in lost:
            lost.remove(i+1)
    
    return n-len(lost)

---

[:] 가 뭘까?

파이썬에서 리스트를 for문으로 돌리면서 동시에 remove()나 append() 같은 수정 작업을 하면 문제가 생길 수 있다.
→ 리스트 인덱스가 바뀌면서, 다음 요소를 건너뛰는 버그가 발생할 수 있음.

잘못된 예시

arr = [1, 2, 3, 4]
for x in arr:
    arr.remove(x)

print(arr)  # [2, 4]  → 절반만 지워짐

x = arr[0] = 1 → remove(1) 실행 → arr = [2,3,4]

이제 for문은 다음 인덱스 arr[1] 을 보려고 하는데, 이미 리스트가 바뀌어서 arr[1] = 3을 읽어옴
→ 결과적으로 2가 건너뛰어짐

x = 3 → remove(3) → arr = [2,4]

이제 for문은 arr[2]를 읽어오는데 arr[2] 는 리스트가 짧아져서 존재하지 않기에 반복 종료

최종적으로 [2,4]가 남게 된다.

안전한 방법

[:] 로 리스트의 복사본을 만들어 순회하면 원본은 마음대로 수정해도 된다.

arr = [1, 2, 3, 4]
for x in arr[:]:   # 복사본 순회
    arr.remove(x)

print(arr)  # []  → 모든 요소 정상 삭제

여기서는 arr를 순회하는것이 아닌, arr[:] 라는 새로운 복사본 [1,2,3,4] 를 순회하며 arr를 remove 하므로, 원본은 전부 제거된다.

---

이 복사본 순회방법을 위 문제에서 사용했다.

for i in reserve[:]:
    if i in lost:
        reserve.remove(i)
        lost.remove(i)

reserve[:] 를 써서 복사본을 순회하기 때문에,
원본 reserve를 안전하게 수정할 수 있었다.