[프로그래머스][Python] 체육복

문제를 정리해보자.

 

여벌의 체육복을 가지고 있는 학생은 체육복이 없는 학생에게 빌려줄 수 있다. 단, 양옆의 학생에게만 빌려줄 수 있다.

하지만 여벌의 체육복을 가지고 있는 학생이 체육복을 도난당했다면 빌려줄 수 없다. (자신이 사용해야 하기 때문이다.)

체육복이 있어야 체육수업을 들을 수 있다. 체육수업을 들을 수 있는 학생의 최댓값을 구해야 한다.

 

 

풀이를 생각해보자.

 

1) 도난당한 학생 => 체육복이 없다.

2) 도난당한 학생이며 여벌이 있는 학생 => 체육복이 있다. 빌려줄 체육복이 없다.

3) 여벌이 있는 학생 => 체육복이 있다. 빌려줄 체육복도 있다.

 

3번 학생만 1번 학생을 빌려주면 된다.

 

 

구현해보자.

 

 

# 전체 학생의 수 : n
# 도난당한 학생들의 번호가 담긴 배열 : lost
# 여벌의 체육복을 가져온 학생들의 번호가 담긴 배열 : reserve

def solution(n, lost, reserve):
    dp = [1] * 32
    new_reserve = []
    count = n - len(lost)

    # 도난 학생
    for num in lost:
        dp[num] = 0

    for num in reserve:
        # 여벌 학생 == 도난 학생
        if dp[num] == 0:
            dp[num] = 1
            count += 1

        # 여벌 학생 != 도난 학생
        else:
            new_reserve.append(num)
    
    lost.sort()
    new_reserve.sort()
    # 체육복 빌려주기
    for num in new_reserve:
        for check in [num-1, num+1]:
            if dp[check] == 0:
                dp[check] = 1
                count += 1
                break
    return count


print(solution(5, [2, 4], [3, 5]))