48. 체육복

유형 : 그리디

풀이 시간 : 20분? 30분

def solution(n, lost, reserve):
    answer = 0
    check = [1 for i in range(n+1)]
    for r in reserve:
        check[r] += 1
    for l in lost:
        check[l] -= 1
    for i in range(1, len(check)):
        if i == len(check)-1 and check[i] == 0:
            if check[i-1] == 2:
                check[i-1] -= 1
                check[i] += 1                
        elif check[i] == 0:
            if check[i-1] == 2:
                check[i-1] -= 1
                check[i] += 1
            elif check[i+1] == 2:
                check[i+1] -= 1
                check[i] += 1
    return n - (check.count(0))

 

check 배열에는 도난 사건 발생 후 i번째 학생의 체육복 갯수를 check[i] 에 저장.

i를 순회하며 

 1) 먼저 앞 학생에게 빌릴 수 있는지 보고

 2) 안 될 경우 뒤 학생에게 빌릴 수 있는지 체크

이 때, 마지막 학생의 경우 앞 학생의 것만 체크한다. 

 

먼저 앞을 체크하고 뒤를 체크하면 (뒤의 경우 뒤 학생에게 빌려줄 수도 있기 때문, 앞은 이미 체크 완료)

최적의 답을 찾을 수 있다. (greedy)