[프로그래머스][Lv1] - 체육복 (그리디 알고리즘)(파이썬/Python)

오답(0점)

def solution(n, lost, reserve):
    answer = list(range(1,n+1))
    
    for i in lost:
        if i in answer:
            answer.remove(i)

    for r in reserve:
        for l in lost:
            if r - l == 1:
                answer.append(reserve.pop(0))
                answer.append(lost.pop(0))
            elif r - l == -1:
                answer.append(reserve.pop(0))
                answer.append(lost.pop(0))
            else:
                reserve.pop(0)
    answer = set(answer)
    
    return len(sorted(list(set(answer)))

• 시간초과가 나온다.
  • 많은 pop(0) 사용이 문제인듯

오답 (60점)

def solution(n, lost, reserve):
    answer = list(range(1,n+1))
    for r in reserve:
        for l in lost:
            if r - l == 1:
                lost.remove(l)
            elif r - l == -1:
                lost.remove(l)
    answer = set(answer)
    
    return len(answer) - len(lost)

• 위의 문제보단 나아졌지만 시간초과가 뜬다.
• 이유는 간단했다 여벌의 체육복을 가지고 있을거라고 생각했던 친구들 역시 도난당했을 수 있다는 문제의 지문을 읽지 않아서이다. 이부분을 아래에서 해결해 풀었다,.

정답

def solution(n, lost, reserve):
    setReserve = set(reserve) - set(lost)
    setLost = set(lost) - set(reserve)
    for r in setReserve:
        if r - 1 in setLost:
            setLost.remove(r-1)

        elif r + 1 in setLost:
            setLost.remove(r+1)
            
    return n - len(setLost)

• 여벌의 옷을 가지고 있다고 생각하는 친구도 도난 당했을 수 있기에 set을 사용해 lost에 있는거라면 해당 숫자를 삭제해주기 위함이다.
  • 위의 굵은 글씨가 이 문제의 핵심이었다.
• 만약 여벌 옷을 가지고 있는 친구들이 도난 당한 경우라면 lost 역시 중복으로 제거해주어야 한다
  • 그 이유는 어차피 빌려줄 수 없기 때문 앞 뒷번호만 찾아보면 된다.
• 여벌 체육복을 가진 친구들을 기준으로 빌려줄 수 있게 한다. 또한 이때 앞자리 숫자부터 메꾸기 위해 r-1부터 검증을 시작해준다! (그래야 더 많은 친구들에게 체육복을 빌려줄 수 있기 때문이다.)
• 참고로 그리디 알고리즘은 어떠한 기준으로 정렬해서 최대의 이득을 보는 법을 구하는 문제이기에 어떻게 정렬해서 풀지?에 초점을 두어야 한다.