[프로그래머스/Python] 탐욕법(그리디) - 체육복

📍 그리디 알고리즘 (탐욕법)

• 현재 상황에서 지금 당장 좋은 것만 고르는 방법
• 매 순간 가장 좋아하보이는 것을 선택하며, 현재의 선택이 나중에 미칠 영향에 대해서는 고려하지 않는다.
• 더 자세히 알아보기

문제

50점 짜리 풀이

• 어려운 문제는 아닌 것 같았는데 접근법이 틀렸다.
• 전체 학생을 나열한 후 잃어버린 학생 번호 제거, 여벌의 체육복을 가지고 있는 학생의 앞 뒤 번호 추가로 구현했다..
• 참 정직한 풀이인듯 최적의 해를 찾기는 글렀다.

def solution(n, lost, reserve):
    nums = [i for i in range(1,n+1)]
    for i in lost:
        if i in nums:
            nums.remove(i)
        if i in reserve:
            reserve.remove(i)
    for i in reserve:        
        if i-1 != 0 and i-1 not in nums:
            nums.append(i-1)
        elif i+1 <= n and i+1 not in nums:
            nums.append(i+1)
    return len(nums)

👩🏻‍🏫 풀이

def solution(n, lost, reserve):
    new_lost = set(lost) - set(reserve)
    # 여벌의 체육복이 있는 학생도 도난 당했을 수도 있다!
    new_reserve = set(reserve) - set(lost)
    for i in new_reserve:
        if i-1 in new_lost:
            new_lost.remove(i-1)
        elif i+1 in new_lost:
            new_lost.remove(i+1)
    return n - len(new_lost)

• 중복을 허용하지 않는 집합 자료형 set을 이용해서 집합 연산을 이용
• - 기호를 이용해 차집합 수행
• 여벌의 체육복을 가지고있는 학생 중에서 잃어버린 학생을 제거한 학생들 즉, 찐으로 빌려줄수있는 학생들! 반복문을 돈다.
  • 여벌의 체육복을 가지고 있는 학생의 앞번호가 잃어버린 학생이라면 (빌려줄 수 있으니까) new_lost.remove(i-1)
  • 앞번호가 잃어버린 학생이 아니고, 뒷번호가 잃어버린 학생이라면 new_lost.remove(i+1)
• 전체 학생에서 잃어버린 학생 수를 빼서 반환