Algorithm/programmers/greedy/level1/체육복 (with python)

📖문제

📝풀이과정

1. 여벌의 체육복을 가져온 학생이 체육복을 도난당한 경우

   • 자신의 체육복 하나를 가져온 경우와 같기 때문에 lost와 reserve 리스트에서 제외하고 시작한다.

2. 여벌의 체육복을 가져온 학생을 순회하면서 도난당한 학생들 체육복 빌려주기

   • 도난당한 학생들에게 체육복을 빌려줄 때는 자신의 앞번호에 있는 학생부터 빌려줘야 한다.
     (만약 뒷번호에 있는 학생부터 빌려준다면 체육수업을 들을 수 있는 학생의 "최댓값"을 구할 수 없다.)

   • 체육복을 빌린 학생은 lost에서 remove해줌 -> 결국 lost에는 체육수업을 들을 수 없는 학생들만 남게된다.

⌨코드

n : 학생의 수
lost : 체육복을 도난당한 학생 번호 리스트
reserve : 여벌 체육복을 가져온 학생 번호 리스트

def solution(n, lost, reserve):
    answer = 0
    
    # 1. 여벌의 체육복을 가져온 학생이 체육복을 도난당한 경우
    for i in reserve[:]:
        if i in lost:
            reserve.remove(i)
            lost.remove(i)
            
    # 2. 여벌의 체육복을 가져온 학생을 순회하면서 도난당한 학생들 체육복 빌려주기
    for j in reserve:
        if j - 1 in lost:
            lost.remove(j - 1)
            continue
        elif j + 1 in lost:
            lost.remove(j + 1)
    
    # 정답은 (전체 학생 수) - (체육복을 도난당하고 빌리지도 못한 학생 수)
    answer = n - len(lost)
    return answer

💡새로 알게된 문법

파이썬 리스트 복사

1. copy 함수 사용
   copy_list = list1.copy()
2. 슬라이싱 사용
   copy_list = list1[:]

• 리스트를 순회할 때 리스트 내용이 변경되는 경우 주의

# 잘못된 코드 -> 원본 리스트를 그대로 사용
for i in reserve:
	if i in lost:
    	reserve.remove(i)
        lost.remove(i)
        
# 맞는 코드 -> 리스트를 복사해서 사용
for i in reserve[:]:
	if i in lost:
    	reserve.remove(i)
        lost.remove(i)

🤔의문점

문제를 풀 때 너무 당연하다는 듯이 lost와 reserve 리스트가 정렬됐다고 생각해서 체육복을 빌려줄 때 앞번호부터 빌려준다고 했는데, 문제에는 입력값이 정렬됐다는 말이 없었다.
만약 reserve가 정렬되어있지 않다면 내가 제출한 코드가 특정한 테스트케이스(예를들어 3번, 5번 학생이 여벌의 체육복을 가지고있고 4번, 6번 학생이 체육복을 도난당했을 경우에 reserve = [3, 5]라면)에서 통과되지 않았을 것이다.
그래서 체육복을 앞번호부터 빌려준다는 규칙을 적용하려면 lost와 reserve를 오름차순으로 정렬하는 코드를 추가하면 좋을 것 같다.