[Python | 파이썬] 체육복 (프로그래머스 GREEDY)

[Python | 파이썬] 체육복 (프로그래머스 GREEDY)

 

 

여분의 체육복을 가져온 학생 중 체육복을 잃어버린 학생은 자신의 체육복을 입어야하므로 reserve 중 lost에 있는 원소를 먼저 제거해 set rst로 여분의 체육복을 가져오고 자신의 체육복을 잃어버리지 않아 빌려 줄 수 있는 학생들을 구한다. 그리고 set los 에서도 그러한 학생들을 지워준다.

앞에서부터 res에 있는 학생의 앞에 있는 학생이 los에 있는지 확인하고 los에서 지워준다. 만약 앞에 있는 학생이 los에 없다면 뒤에 있는 학생이 los에 있는지 확인하고 los에서 지워준다. 

이 문제는 그리디이기 때문에 앞에있는 학생부터 먼저 확인하고 체육복을 빌려줘야 최적의 답을 구할 수 있다.

 

def solution(n, lost, reserve):
    res = set(reserve) - set(lost)
    los = set(lost) - set(reserve)
    for r in res:
        if r-1 in los:
            los.remove(r-1)
        elif r+1 in los:
            los.remove(r+1)
    
    return n-len(los)

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