탐욕법(greedy, 프로그래머스 - 체육복)
배경
프로그래머스 “체육복” 문제를 풀고 나서, 더 나은 풀이가 있을 것 같아서 오늘도 커서를 켰다.
구현
def solution(n, lost, reserve):
result = 0
rented = {}
for current in range(1, n + 1):
if current not in lost:
result += 1
elif current in reserve:
result += 1
elif (
current - 1 in reserve
and current - 1 not in lost
and current - 1 not in rented
):
rented[current - 1] = True
result += 1
elif (
current + 1 in reserve
and current + 1 not in lost
and current + 1 not in rented
):
rented[current + 1] = True
result += 1
return result
이 문제를 풀기 위해 내가 선택한 방법은 1번 학생부터 수업에 참여할 상황이 되는지 한 명씩 판별해 보는 것이었다. 여기서 주의할 점은 학생을 오름차순으로 비교하기 때문에, 앞의 학생에게 빌릴 수 있는지부터 확인한 후, 뒤의 학생에게 빌릴 수 있는지 확인해야한다는 점이다. 왜냐하면 앞의 학생은 어떤 상황이든 자신이 수업에 참여할 수 있으면 이미 참여했을 것이기 때문에, 그 학생에게 빌릴 수 있다면 그게 가장 최선의 선택이기 때문이다.
일단 위의 코드로도 채점은 통과가 됐다. 하지만 딱 봐도 개선의 여지가 많아 보인다.
개선
아래는 Cursor가 개선해 준 코드다.
def solution(n, lost, reserve):
# 여벌 체육복이 있는 학생이 도난당한 경우를 먼저 처리
reserve_only = set(reserve) - set(lost)
lost_only = set(lost) - set(reserve)
# 체육복을 빌려줄 수 있는 경우를 처리
for r in reserve_only:
if r - 1 in lost_only:
lost_only.remove(r - 1)
elif r + 1 in lost_only:
lost_only.remove(r + 1)
# 전체 학생 수에서 체육복을 잃어버린 학생 수를 뺀 값이 체육수업을 들을 수 있는 학생의 최댓값
return n - len(lost_only)
reserve에서 여벌이 있지만 도난 당한 학생을 미리 제거하고(reserve_only), lost에서도 여벌이 있으면서 도난 당한 학생을 제거한다(lost_only). 왜냐면 여벌이 있는데 도난 당한 학생은 조용히 수업에 참석하면 그만이기 때문이다.
그렇게 한 후, 진짜 여벌이 있는 학생들을 순회하면서 만약 체육복을 빌렸다면 lost_only에서 제거해주는 방식으로 수업을 참석시키고, 마지막에는 결국 체육복이 없는 학생만 전체 학생수(n)에서 빼주면 되는 거였다.
결과
아래는 Cursor의 설명이다.
- 여벌 체육복이 있는 학생이 도난당한 경우 처리:
reserve와lost의 교집합을 제거하여 실제로 여벌 체육복을 빌려줄 수 있는 학생(reserve_only)과 체육복이 없는 학생(lost_only)을 구합니다.- 체육복 빌려주기:
reserve_only에 있는 학생이 앞뒤로 체육복을 빌려줄 수 있는 경우를 확인하여 lost_only에서 해당 학생을 제거합니다.- 결과 계산: 전체 학생 수에서 체육복을 잃어버린 학생 수를 뺀 값을 반환하여 체육수업을 들을 수 있는 학생의 최댓값을 구합니다. 이 방법은 탐욕법을 사용하여 가능한 한 많은 학생이 체육수업에 참여할 수 있도록 체육복을 빌려주는 최적의 방법을 찾습니다.
Cursor의 코드를 보면서 파이썬답게 간결한 코드를 짜는 습관을 들여야겠다고 생각했다.