[고득점 Kit / 탐욕법 ] 체육복

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

프로그래머스

 

이 문제는 다음의 흐름으로 풀었다.

 

 

• 전체 학생 수 - 체육복을 잃어버리고 빌리지 못한 학생수를 빼면 그게 답이다.
• 먼저 lost와 reserve에 모두 포함된 학생들은 체육복을 하나 잃었지만 여벌이 있으므로 다른 학생에게 빌려줄 수 없으므로 차집합을 이용하여 계산에 의미가 없는 학생들은 전부 제외시켜준다.(우리가 구하고자 하는 것은 체육복을 잃어버렸으면서 빌리지 못한 학생수를 구하는 것이고, 애초에 여벌이 있는 학생들은 빌릴 필요가 없으므로)
• 남은 lost 학생들에 대해 앞번호나 뒷번호에 있는 reserve 학생에게 체육복을 빌릴 수 있는지 확인한다.

 

코드를 보자.

def solution(n, lost, reserve):
    # 여벌을 가진 학생이 도난당한 경우를 처리
    lost_set = set(lost) - set(reserve) # set을 붙이는 이유는 리스트끼리는 차집합 계산이 불가능하므로!
    reserve_set = set(reserve) - set(lost)
    
    # 체육복을 빌려줄 수 있는 경우를 처리
    for r in sorted(reserve_set):
        if r - 1 in lost_set:
            lost_set.remove(r - 1)
        elif r + 1 in lost_set:
            lost_set.remove(r + 1)
    
    # 전체 학생 수에서 체육복을 잃어버리고 빌리지 못한 학생을 뺀다
    return n - len(lost_set)

 

 

 

	lost_set = set(lost) - set(reserve)
    reserve_set = set(reserve) - set(lost)

 

위와 같이 set함수를 이용하여 차집합을 구했다. (리스트끼리는 빼기 연산이 불가하므로 set함수를 이용)

• lost_set: 여벌이 없어서 체육복을 빌려야 하는 학생들.
• reserve_set: 다른 학생에게 체육복을 빌려줄 수 있는 학생들.

 

for r in sorted(reserve_set):  # 여벌을 가진 학생 번호를 정렬하여 하나씩 확인
    if r - 1 in lost_set:  # 여벌을 가진 학생의 바로 앞번호 학생이 체육복을 잃어버렸다면
        lost_set.remove(r - 1)  # 그 학생에게 체육복을 빌려주고 lost_set에서 제거
    elif r + 1 in lost_set:  # 앞번호가 없으면, 바로 뒷번호 학생이 체육복을 잃어버렸다면
        lost_set.remove(r + 1)  # 그 학생에게 체육복을 빌려주고 lost_set에서 제거

 

 

• sorted(reserve_set): 여벌 체육복을 가진 학생들의 번호를 정렬한다. 예를 들어, reserve_set에 {3, 5, 1}이 있으면, 정렬 후 [1, 3, 5]가 된다. 이렇게 정렬하는 이유는 앞번호 학생에게 우선적으로 체육복을 빌려주기 위해서다.
• if r - 1 in lost_set: 여벌 체육복을 가진 학생 r의 바로 앞번호 학생이 체육복을 잃어버렸는지 확인한다. 예를 들어, 3번 학생이 여벌을 가지고 있을 때, 2번 학생이 도난당했으면 그 학생에게 체육복을 빌려준다.
  • 빌려주면 체육복을 빌린 학생은 더 이상 체육복이 필요하지 않으므로 lost_set에서 제거한다.
• elif r + 1 in lost_set: 만약 바로 앞번호 학생이 체육복이 필요하지 않다면, 뒷번호 학생이 체육복을 잃어버렸는지 확인한다. 만약 4번 학생이 도난당했으면 그 학생에게 체육복을 빌려준다.