[프로그래머스💯] 코딩테스트 연습 > 탐욕법(Greedy) > 체육복

<프로그래머스 문제풀이>

 

---

해답)

def solution(n, lost, reserve):
    # 그리디한 알고리즘 이므로 소트를 해줘야한다.
    reserve.sort()
    # 여벌이 있는 친구가 도난당한 경우
    for i in reserve:
        if i in lost:
            lost.remove(i)
            reserve[reserve.index(i)] = -5
    # 체육복을 빌려주는 경우
    for i in reserve:
        if i-1 in lost:
            lost.remove(i-1)
        elif i+1 in lost:
            lost.remove(i+1)
    return n-len(lost)

 

* 알고리즘 순서

여벌이 있는 친구들을 기준으로 (정렬이 되어있음을 가정) 빌려줄수있는 앞번호 부터 쭈욱 빌려준다.

1. 자신이 잃어버린경우

2. 자신의 앞번호가 잃어버린 경우

3. 자신의 뒷번호가 잃어버린 경우

 

빌려준 뒤에는 인덱스 값을 음수로 바꿔주고

빌린 학생은 lost 목록에서 삭제해 버린다.

 

출처: 프로그래머스 코딩 테스트 연습, https://programmers.co.kr/learn/challenges