[Python] 프로그래머스 / level 1 / 체육복 / 그리디 / 반례

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

프로그래머스

 

 

def solution(n, lost, reserve):
    answer = 0
    
    only_one = n-len(lost) # 한벌만 있는 학생들
    
    for l in lost:
        if l in reserve:
            reserve.remove(l)
            lost.remove(l)
            
    for i in reserve:
        if i+1 in lost:
            lost.remove(i+1)
            reserve.remove(i)
            only_one += 1
        elif i-1 in lost:
            lost.remove(i-1)
            reserve.remove(i)
            only_one += 1

    return only_one

 

다음과 같이 풀 경우 테케는 다 맞지만 채점 후의 결과는 대부분 틀린다.

그 이유를 알아보니

 

for문은 리스트의 길이만큼 반복 동작을 하게 되는데 리스트의 원소를 제거하면 리스트의 길이가 바뀐다.

하지만 for문은 리스트의 길이가 바뀌었다는 것을 감지하지 못하고 기존 리스트의 길이만큼 반복하게 되므로 오동작 할 가능성이 매우 높아지기 때문이다.

 

반례 : n = 5, lost = [4, 2] , reserve = [5, 3], answer = 5

 

 

def solution(n, lost, reserve):
    
    # 여벌 체육복을 가져왔는데 도난 당한 경우 제외 -> reserve랑 lost랑 중복 없애기
    two = [r for r in reserve if r not in lost]
    
    # 체육복을 빌릴 수 있는 학생들 -> reserve랑 lost 중복 없애기
    rent = [l for l in lost if l not in reserve]
    
    two.sort()
    rent.sort()
    
    for idx in two:
        if idx-1 in rent:
            rent.remove(idx-1)
        elif idx+1 in rent:
            rent.remove(idx+1)
    
    return n-len(rent)

 

위와 같은 반례가 있기 때문에 정렬을 해줘야 하며 reserve에 3이 있다면 최적의 해를 위해 lost에 2가 있을 경우를 먼저 고려해야 하기 때문에 idx-1을 먼저 해야 한다!!(elif에 idx-1 먼저 했다가 틀림)