[Greedy] 체육복

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

프로그래머스

 

제한사항 중 "여벌 체육복을 가져온 학생이 체육복을 도난당했을 수 있습니다. 이때 이 학생은 체육복을 하나만 도난당했다고 가정하며, 남은 체육복이 하나이기에 다른 학생에게는 체육복을 빌려줄 수 없습니다."가 있기 때문에

lost와 reserve 리스트 중 중복되는 부분을 먼저 삭제하고, answer 값을 n - len(lost)로 초기화합니다.

 

이후에 체육복을 빌려줄 수 있는지 if r - 1 == l or r + 1 == l을 통해 확인하고, answer값을 증가시킵니다.

def solution(n, lost, reserve):
    del_list = []
    
    for l in lost:
        for r in reserve:
            if l == r:
                del_list.append(l)
    
    for d in del_list:
        lost.remove(d)
        reserve.remove(d)
    
    answer = n - len(lost) 
                
    for l in lost:
        for r in reserve:
            if r - 1 == l or r + 1 == l:
                answer += 1
                reserve.remove(r)
                break
                
    return answer

그런데 테스트 케이스 중 13, 18번이 실패로 채점되었습니다. 생각해보니 문제 설명에서는 입력 데이터가 정렬된 리스트라고 표기하지 않았습니다. '체육복'과 같은 문제는 그리디(Greedy)로 문제를 해결할 때 반드시 리스트가 정렬되어 있어야 한다는 전제 조건이 필요했습니다. 소스 코드에서도 체육복을 빌려줄 수 있는지 판단할 때, 빌려줄 수 있으면 바로 빌려주면서 answer값을 증가시키기 때문에, 리스트가 정렬되어 있지 않다면 올바른 정답을 계산할 수 없습니다.

 

 

따라서 아래와 같이 리스트 정렬 코드를 삽입해줍니다.

def solution(n, lost, reserve):
    lost.sort()			# 정렬	
    reserve.sort()		# 정렬
    
    del_list = []
    
    for l in lost:
        for r in reserve:
            if l == r:
                del_list.append(l)
    
    for d in del_list:
        lost.remove(d)
        reserve.remove(d)
    
    answer = n - len(lost) 
                
    for l in lost:
        for r in reserve:
            if r - 1 == l or r + 1 == l:
                answer += 1
                reserve.remove(r)
                break
                
    return answer

또한 중복을 제거하는 부분도 위와 같이 for l in lost로 작성하는 것이 아니라, 다음과 좀 더 간단하게 작성할 수 있습니다.

def solution(n, lost, reserve):
    lost.sort()
    reserve.sort()
    
    for l in lost[:]:
        if l in reserve:
            reserve.remove(l)
            lost.remove(l)
    
    answer = n - len(lost) 
                
    for l in lost:
        for r in reserve:
            if r - 1 == l or r + 1 == l:
                answer += 1
                reserve.remove(r)
                break
                
    return answer

for l in lost[:]는 for l in lost로 작성하면 채점에서 실패를 얻을 수 있습니다. for l in lost는 코드가 실행될 때, lost 리스트의 크기만큼 반복하기 때문에 lost.remove(l)를 실행할 경우 전체 lost를 반복할 수 없습니다.

 

따라서 for l in lost[:]를 통해 remove()가 됐을 때, lost의 전체 원소를 모두 반복에 사용할 수 있도록 작성해야 합니다.