[프로그래머스] 체육복

[프로그래머스] 체육복

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

문제 설명

· 여벌 체육복이 있는 학생이 체육복을 도난당한 학생한테 체육복을 빌려주고자 함

· 체육복은 앞번호나 뒷번호의 학생에게만 빌려줄 수 있음

· 여벌 체육복이 있는 학생이 체육복을 도난당했을 경우 체육복을 빌려줄 수 없음

· 최대로 체육복을 가질 수 있는 학생 수를 return

정리하면 체육복을 빌려주는 우선순위를 잘 생각해서 체육복을 가진 학생이 최대로 되게 하는 문제

접근 방법

· 왼쪽부터 순회한다고 가정하고, 체육복을 빌려주고자 하는 학생 양 옆의 학생이 체육복을 도난당했을 때, 왼쪽의 학생은 체육복을 받을 수 있는 마지막 기회

· 따라서 여분의 체육복을 가진 사람들이 빌려줘야 할 우선순위는 왼쪽 > 오른쪽 (왼쪽부터 시작했을 때 기준)

· 체육복을 빌려줄 수 있는 학생들이 왼쪽에 있는 학생을 우선순위로 빌려줬을 때, 체육복을 가진 학생들이 최대

· 그리디 알고리즘의 예

알고리즘 설계 및 구현

def solution(n, lost, reserve):
    # 여분의 체육복을 가진 학생들 중에서 도난당한 학생들을 제외한 리스트 생성
    lost_new = list(set(lost) - set(reserve))
    
    # 도난당한 학생들 중에서 여분의 체육복을 가진 학생들을 제외하고 오름차순으로 정렬된 리스트 생성(왼쪽부터 순회하기 위함)
    reserve_new = sorted(list((set(reserve) - set(lost))))

    # 여분의 체육복을 가진 학생들이 도난당한 학생들에게 체육복을 빌려주는 과정
    for i in reserve_new:
        if i - 1 in lost_new:
            lost_new.remove(i - 1)  # 왼쪽에 있는 도난당한 학생에게 빌려줌
        elif i + 1 in lost_new:
            lost_new.remove(i + 1)  # 오른쪽에 있는 도난당한 학생에게 빌려줌

    # 체육복을 입을 수 있는 학생의 수를 계산하여 반환
    return n - len(lost_new)

결과

개선 사항

lost = list(set(lost) - set(reserve))
reserve = sorted(list((set(reserve) - set(lost))))

· 변수 이름 그대로 썼다가 왜 차집합이 안구해지는지 고민하며 시간낭비
· 변수 이름 신경 써서 지을 것