코딩테스트 연습 - 체육복(탐욕법)

코딩테스트 연습 - 체육복(탐욕법)

체육복을 도난당했다. 여분의 체육복이 있는 학생이 자신의 앞뒤 번호 학생에게 체육복을 빌려줄 수 있다. 체육수업을 최대로 들을 수 있는 학생 수를 반환하라.

# 오류코드

합계: 75.0 / 100.0 : 테스트케이스 5,7,12 실패
=> 앞의 학생을 먼저 체크하는게 더 효율적

합계: 91.7 / 100.0 : 테스트케이스 12 실패

def solution(n, lost, reserve):
    l_lost = len(lost)
    for i in lost:
        if i in reserve: # 여벌 체육복 있는 학생이 도난
            l_lost -= 1
            reserve.remove(i)
        elif i-1 in reserve:
            l_lost -= 1
            reserve.remove(i-1)
        elif i+1 in reserve:
            l_lost -= 1
            reserve.remove(i+1)
    return n-l_lost

# 정답코드

정렬을 한거랑 안한거랑 검사하는 횟수가 달라지는 건지 잘 모르겠지만 lost와 reserve를 정렬하니까 정답이였다.

def solution(n, lost, reserve):
    lost = sorted(lost)
    reserve = sorted(reserve)
    l_lost = len(lost)
    for i in lost:
        if i in reserve: # 여벌 체육복 있는 학생이 도난
            l_lost -= 1
            reserve.remove(i)
        elif i-1 in reserve:
            if i-1 not in lost:
                l_lost -= 1
                reserve.remove(i-1)
        elif i+1 in reserve:
            if i+1 not in lost:
                l_lost -= 1
                reserve.remove(i+1)
    return n-l_lost

O(nlogn) + O(nlogn) + O(n)O(n) + O(n)O(n)O(n) + O(n)O(n)*O(n) => O(n^3)

# 참고코드

풀고나서 훨씬 깔끔해보이는 코드를 가져와봤다. 중복되는 학생을 배열에서 미리 제거해준 것으로 보인다. 한줄 for문이 문제풀 때 은근 유용하게 사용되는 것 같다.
ex) _reserve = [r for r in reserve if r not in lost]

def solution(n, lost, reserve):
    _reserve = [r for r in reserve if r not in lost]
    _lost = [l for l in lost if l not in reserve]
    for r in _reserve:
        f = r - 1
        b = r + 1
        if f in _lost:
            _lost.remove(f)
        elif b in _lost:
            _lost.remove(b)
    return n - len(_lost)

O(n)*O(n) => O(n^2)

#set을 이용하면 O(n)으로도 짤 수 있다고 한다. 나중에 더 연습해보기!