체육복

문제

문제

처음 작성한 코드

#5,7 Non Pass
def solution(n, lost, reserve):
    have = [1]*n # 체육복 가진 사람=1 아니면 0
    give = [0]*n # 빌려준 사람=1 아니면 0 -> 두 번 빌려줌을 방지하기 위해
    reserve = [i-1 for i in reserve] # index 헷갈려서 -1 함
    for i in lost:
        have[i-1] = 0 # lost면 체육복 안가졌으니 flag=0 
    for i in reserve: #여분 가진 사람
        if give[i]==0:
            if have[i]==0: have[i]=1
            elif i==n-1:
                if have[i-1]==0: have[i-1]=1
            elif i==0:
                if have[i+1]==0: have[i+1]=1
            else:
                if have[i-1]==0:have[i-1]=1
                elif have[i+1]==0: have[i+1]=1
            give[i]=1
    return have.count(1) 

 

코드 리뷰 후

def solution(n, lost, reserve):
    _lost = [i for i in lost if i not in reserve]
    _reserve = [i for i in reserve if i not in lost]
    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)

 

깨달은 점

너무 어렵게 생각했다.. -> 처음 작성한 코드 개판..

탐욕법이 도대체 뭔지 모르겠다..

테스트 케이스 5,7 번에서 NP 떠서 고민고민하고 있었는 데, 연주(내친구)가 반례를 찾아줬다..

제한사항중에 "여벌 체육복을 가져온 학생이 도난당할 수 있다." 라는 표현때문에 

reserve를 돌면서 i+1, i-1 에게 빌려주기전에 i인 자신에게 먼저 빌려주면 된다고 생각했는데 생각이 짧았다.

  -> 반례) solution(5, [3,4,5],[2,3,4]) 이렇게 되면 2가 3한테 먼저 빌려주게 되어버리니까 내가 생각한대로 구현하기 위해서는 for 문을 돌기전에 lost와 reserve에 공통적으로 있는 3,4 를 없애주고 시작하는 것이 맞다.