[Python] 프로그래머스 42862. 체육복 (Lv.1)

https://school.programmers.co.kr/learn/courses/30/lessons/42862

프로그래머스

 

Greedy 유형의 연습문제입니다.

여분의 체육복을 누구에게 빌려줄지가 중요할것 같지만, 앞에서부터 가능한 경우를 채워가면 풀이가 가능합니다.

만약 뒤에서 체육복이 필요하게 되면 앞의 체육복을 빼앗아야 하는데 앞의 체육복을 뺏는 경우는 어차피 총합은 같은 제로섬 동작이고 뒤에서 빌리는게 가능하면 최대값이 바뀌므로 가능한한 앞쪽부터 채우는게 유리합니다.

 

주의할 점은 여분의 체육복이 있는 상태에서 체육복을 도둑맞는 경우 무조건 자신이 착용한다는 것을 구현해줘야 합니다.

이 경우는 체육복의 수가 줄어들 수 있습니다.

Ex) 3번과 4번이 여벌을 소유하고 2,3번이 체육복을 도둑맞는 경우 1번(자기것) 2번(3번의 것) 3번(4번의 것) 4, 5번으로 5명 모두 체육복을 입을 수 있지만 문제의 조건에서 3번은 자기가 우선적으로 자기것을 입습니다. 즉 2번은 3번의 여벌 체육복을 빌리지 못해 답은 4가 됩니다.

 

def solution(n, lost, reserve):
    answer = 0
    student = [True for i in range(n)]
    spair = [False for i in range(n)]
    
    for i in lost:
        student[i-1] = False
    
    for i in reserve:
        if student[i-1]:
            spair[i-1] = True
        else:
            student[i-1] = True
        
    
    for i in range(n):
        if student[i]:
            answer += 1
        
        else:
            for j in range(-1,2):
                if 0 <= i+j < n and spair[i+j]:
                    spair[i+j] = False
                    answer += 1
                    break
    
    return answer