프로그래머스 | 체육복 (파이썬) 그리디, SET 차집합

 

오늘도 오랑이는 문제를 풉니다.

 

체육복

풀이 과정

• 여분 체육복 학생이 도난 당하면 빌려줄 수 없음 → reserve 와 lost 의 공통 숫자 제거
• lost와 reserve 를 비교해서 가장 작은 수부터 제거 (그리디)
• answer 는 n - lost 개수

우선 마지막 제한사항을 보면 여벌 체육복이 있는 학생이 도난당했을 경우, 해당 학생은 다른 학생에게 옷을 빌려줄 수 없게 된다는 조건이 있습니다. 

이를 다른 말로 해석해보면, lost 와 reserve 에 같은 숫자가 있을 경우 해당 숫자는

1) 옷을 빌려줄 수 없기 때문에 reserve 에서 제거해야 하고 

2) 이미 여분이 있기 때문에 옷을 빌릴 필요가 없어서 lost 에서도 제거해야 합니다. 

 

즉 lost와 reserve 의 교집합을 제거하면 되는데, 지난 문제에서 set 함수의 교집합을 사용했던 거와 비슷하게 이번에는 차집합으로 lost와 reserve 의 공통된 숫자를 제거해줍니다. 

이때 기존 lost ,reserve 를 대체해버리면 뒤에 코드에서 오류가 생기기 때문에 새로운 변수에 저장해줘야 합니다.

def solution(n, lost, reserve):
    reserve_del = set(reserve) - set(lost)
    lost_del = set(lost) - set(reserve)

 

겹치는 수를 제거했다면 그리디 기법으로 lost에서 작은 수부터 하나씩 제거해주고, 남은 lost 의 개수만큼 answer 에서 뺀 값이 답이 됩니다. 

 

lost_del 의 요소에 대해 반복 루프를 만들게 되면, remove 를 진행한 후에 lost_del 이 변경되는 구조이기 때문에 반복문 수행에 오류가 나며 코드가 실행되지 않습니다.  

for i in lost_del:
    if (i-1) in reserve_del:
        lost_del.remove(i)
    elif (i+1) in reserve_del:
        lost_del.remove(i)

 

 

그렇기 때문에 lost_del 대신 reserve_del 의 요소를 기준으로 반복문을 짜줍니다. 

for i in reserve_del: 
    if i-1 in lost_del:
        lost_del.remove(i-1) 
    elif i+1 in lost_del: 
        lost_del.remove(i+1)

 

마지막으로 최종 체육 수업을 들을 수 있는 학생 수를 구합니다. 

 

최종 코드

def solution(n, lost, reserve):
    reserve_del = set(reserve) - set(lost)
    lost_del = set(lost) - set(reserve)
    
    for i in reserve_del: 
        if i-1 in lost_del:
            lost_del.remove(i-1) 
        elif i+1 in lost_del: 
            lost_del.remove(i+1)
            
    answer = n - len(lost_del)
    return answer

 

 

 

오랑우탄이 영어를 하고 오랑이가 코드마스터가 되는 그날까지~

 

 

프로그래머스