탐욕법 (greedy) - 체육복

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

근데 그래도 정렬해서 주지않을까? 하고 정렬안하고 쭉 풀어봤다.

초기 코드

def solution(n, lost, reserve):
    answer = n - len(lost)
    lost.sort(reverse = True)
    for l in lost:
        for r in reserve:
            if l - r < 0:
                answer+=1
                break
            elif l - r == 0:
                answer-=1  
                break
    return answer

응 어림없어~ 테케에서 다 걸려짐.
머리 싸매면서 풀이도 보고 하니까 보이는 점.

문제를 똑바로 읽자..
전에 내 블로그에서 풀었던 방식을 보니까 set 의 연산을 통해 쉽게 끝낼 수 있었다.
국어 좀 잘하자 제발 ^^

def solution(n, lost, reserve):
    lost.sort() # 정렬
    reserve.sort() # 정렬  
    _reserve = list(set(reserve)-set(lost))
    _lost = list(set(lost)-set(reserve))
    for r in _reserve:
        if r+1 in _lost: # 내 뒷번호니까 빌려줌
            _lost.remove(r+1)
        elif r-1 in _lost:
            _lost.remove(r-1)
    return n - len(_lost)

엥 근데 아직도 100점은 맞지 못하고 있다.
어디 테스트케이스에서 걸리는 듯했다.

reserve를 reverse 했더니 해결

def solution(n, lost, reserve):
    
    _reserve = list(set(reserve)-set(lost))
    _lost = list(set(lost)-set(reserve))
    
    _reserve.sort(reverse=True)
    _lost.sort()

    for r in _reserve:
        if r+1 in _lost: # 내 뒷번호니까 빌려줌
            print(r+1, lost) # 확인용
            _lost.remove(r+1)
        elif r-1 in _lost:
            print(r-1, lost) # 확인용
            _lost.remove(r-1)
    return n - len(_lost)

5, [4, 2], [3, 5] 를 생각해보자.
그러면 _reserve = [3,5]

3부터 시작하면 4에서 빌려주고 2에서는 못 빌려줌
그다음 5는 아무도 빌려줄 수 없음
오히려 5부터 시작을 하면 4한테 빌려주고
3은 2한테 빌려줄 수 있음.