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

def solution(n, lost, reserve): 
    students = [1 for i in range(n)]
    for r in reserve:
        students[r-1] += 1
    for l in lost:
        students[l-1] -= 1
        
    for i in range(n):
        if students[i] == 2:
            if i>0 and students[i-1] == 0:
                students[i-1] = 1
                students[i] = 1
            elif i<len(students)-1 and students[i+1] == 0:
                students[i+1] = 1
                students[i] = 1
                
    return len(list(filter(lambda x: x>0, students)))

<내 풀이 분석>

체육복이 없는 학생(체육복 도둑맞은 학생)/ 여분 체육복이 있는 학생/ 체육복

1. 모든 학생의 체육복개수를 저장한 배열 students를 만듦. 처음엔 모두 체육복이 1개씩 있다고 가정

   students = [1,1,1,1,1, ...]

2. 여분의 체육복이 있는 학생의 값 +1 해주기

   students = [1,1,2,2,1,2, ...]

3. 체육복을 도둑맞은 학생의 값 -1 해주기

   students = [0,1,1,2,0,1, ...]

4. 여분의 체육복이 있는 학생(체육복 2개) => 왼쪽학생의 체육복 개수가 0개라면 여분의 체육복을 줌.

5. 왼쪽학생이 체육복이 필요없다면(elif), 오른쪽 학생이 체육복이 필요한지 확인, 개수 0개라면 여분의 체육복을 줌

6. 체육복 개수가 1개 이상이면 수업 참여가능 -> filter로 리턴

 

 

해당 문제는 여분 체육복을 가진 학생이 최대한 많은 학생에게 체육복을 줘야함. 그래서 첫 번째 if 문은 여분 체육복을 가진 학생이 기준이 되어야하는 것 같다. (처음 문제를 풀 때는 체육복이 없는 학생이 여분 체육복이 있는 학생에게 체육복을 받는 식으로 코드를 짰는데, 틀렸다...)

 

 

 

 

+) 틀렸던 풀이

def solution(n, lost, reserve): 
    _reserve = list(set(reserve)-set(lost))
    _lost = list(set(lost)-set(reserve))
    
    _reserve.sort()
    _lost.sort()
    
    for r in list(_reserve):
        if r-1 in _lost:
            _lost.remove(r-1)
        elif r+1 in _lost:
            _lost.remove(r+1)
    
    return n-len(_lost)

1. 교집합(여분체육복이 있는데 도둑맞은 경우)은 체육복이 1개이므로 체육복을 받을 필요도 없고 줄 수도 없으므로 reserve와 lost에서 빼준다.

2. sort()로 정렬해준다.(탐욕 알고리즘이므로 정해진 순서가 중요)

3. _reserve의 값들을 기준으로 왼쪽이 체육복이 없다면 체육복을 준 것으로 취급, _lost에서 해당 값을 삭제해준다.

4. 왼쪽이 체육복이 있고(elif) 오른쪽이 체육복이 없다면 _lost에서 해당 값 삭제

5. 전체 학생에서 체육복이 없는 학생(_lost)의 수를 빼준다.

 

 

■ 내가 틀렸었던 이유

1. reserve를 새로운 _reserve로 사용하지 않고 그냥 reserve로 사용했더니 답이 틀렸다.

   # reserve = list(set(reserve)-set(lost))   => 이 과정에서 문제가 생겼던 것 같다.

2. sort()를 해주지 않았다. 문제에 기술된 간단한 예시를 보면 오름차순으로 정렬되어 있어서, 당연히 정렬된 상태인 줄 알았다. 예상하지 못함.

3. 체육복이 없는 애들을 기준으로 생각함. 여분 체육복을 많이 나눠주는 방향으로 생각했어야 했음.