[프로그래머스 42862 파이썬] 체육복 (level 1, 그리디)

알고리즘 유형 : 그리디
풀이 참고 없이 스스로 풀었나요? : X

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

20230219 추가

def solution(n, lost, reserve):
    answer = 0
    inven = [1]*(n+1)
    for s in lost:
        inven[s] -= 1
    
    for r in reserve:
        inven[r] += 1
    
    for i in range(1, n+1):
        if inven[i] == 0:
            if inven[i-1] == 2:
                inven[i] += 1
                inven[i-1] -= 1
            elif i < n and inven[i+1] == 2:
                inven[i] += 1
                inven[i+1] -= 1
    
    for e in inven[1:]:
        if e != 0:
            answer += 1
    
    return answer

소스 코드(파이썬)

def solution(n, lost, reserve):
    answer = 0
    
    lost_set = set(lost) - set(reserve)
    reserve_set = set(reserve) - set(lost)
    
    for s in reserve_set:
        if s-1 in lost_set:
            lost_set.remove(s-1)
        elif s+1 in lost_set:
            lost_set.remove(s+1)
    
    answer = n - len(lost_set)
    
    return answer

풀이 요약

1. 먼저 체육복 여벌을 가지고 있는데 본인 체육복을 도난당한 학생을 생각해보자.

   이 경우 여벌 체육복을 본인이 써야하므로, 이 때 이 학생은 체육수업을 들을 수 있고 여벌 체육복은 없는 상태가 된다.

   즉, lost와 reserve 두 리스트에서 이 학생은 제외되어야한다. 이를 위해 set의 차집합을 수행한다.

2. 그 외의 경우를 생각해보자.

   아래 테스트 케이스를 보자.

   n = 5, lost = [2,4], reserve = [3, 5]

   만약 3이 4한테 체육복을 주면, 2는 아무한테도 체육복을 못 받는다. 반면 3이 2한테 체육복을 주면, 4는 5한테 체육복을 받을 수 있다.

   이를 일반화해서 생각하면, 여분을 가진 학생은 자신보다 작은 학생부터 우선적으로 체육복을 주려고 해야한다. (reserve 오름차순 정렬 기준)

   reserve의 가장 작은 값의 학생부터 순회하면서 체육복 지급을 계산해본다고 하면, 가장 작은 값의 학생 n이 n-1에게 체육복을 줘버린다고 해도, 위 예제의 한 경우처럼 손해보는 경우가 없다. 만약 안 주게되면 n-1에게 체육복을 줄 학생이 반드시 없기 때문이다.

3. 이 과정을 reserve_set의 모든 원소에 대해 수행하면, lost_set에 아직 지워지지 않고 남은 학생들이 있는데 이는 체육수업을 못 듣는 학생들이다. 따라서, 답은 n - len(lost_set)이다.

배운 점, 어려웠던 점

• 여벌이 있고 도난을 당한 학생의 경우를 set의 차집합을 이용하여 고려해주는 아이디어를 생각지못했다.

• 처음에 리스트로 구현했는데, 리스트에서 원소의 삭제는 비효율적이다보니 index를 활용해서 풀려고했는데 잘 안돼서 다른 사람 풀이를 참고했다.