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

체육복

level1-그리디-체육복

def solution(n, lost, reserve):
    #전체 학생 수 n
    #체육복 없는 학생 리스트 lost
    #여벌 체육복 있는 학생들의 번호 reserve
    res = [1] * (n+1)
    for x in lost:
        res[x] -= 1
    for x in reserve:
        res[x] += 1
    
    for i in range(1,n+1):
        if res[i] == 0: #빌려야함
            if i-1 >= 1 and res[i-1] == 2:
                res[i-1] -= 1
                res[i] += 1
            elif i+1 <= n and res[i+1] == 2:
                res[i+1] -= 1
                res[i] += 1
                
    
    cnt = 0
    for i in range(1,n+1):
        if res[i] >= 1:
            cnt += 1
    return cnt

😀 코멘트

해당 문제는 그리디로 최적의 해를 찾으면 쉽게 풀 수 있다. 근데 나는 무의식적으로 위와 같이 썼는데 중요한 포인트가 하나 있었다. 그건 바로 내가 체육복을 빌려야 하는 상황(res[i] == 0)일 때 왼쪽 학생한테 먼저 확인해야 한다는 것이다.

그 이유는 왼쪽이 아닌 오른쪽한테 빌린다면 그 다음 사람이 못빌리는 상황이 발생할 수도 있다 !!
그렇기에 매번 왼쪽부터 확인해야 한다.