프로그래머스 체육복 (파이썬)

Level 1 Greedy(탐욕법)

 

문제 : https://programmers.co.kr/learn/courses/30/lessons/42862?language=python3# 

코딩테스트 연습 - 체육복

 

첫번째 정답 코드

def solution(n, lost, reserve):
    answer = 0
    reserve.sort()
    lost.sort()
    temp = reserve[:]

    for i in reserve:
        if i in lost:
            lost.remove(i) 
            temp.remove(i)

    reserve = temp[:]
    for i in reserve:
        if lost:
            for j in range(len(lost)):
                if i == lost[j]-1:
                    lost.pop(j)
                    break

                elif i == lost[j]+1:
                    lost.pop(j)
                    break

        else:
            break
        
    answer = n - len(lost)
    return answer

먼저 reserve와 lost를 모두 정렬하고 앞에서부터 낮은 번호의 학생이 빌려주게 만들었습니다.

그 후 자신의 체육복이 도난당한 경우 두 리스트에서 제외 시켰습니다.

lost를 처음부터 끝까지 탐색하며 앞 뒤 번호가 맞으면 pop(인덱스로) 빼주었습니다.

하지만 위 코드는 가독성이 좋지 않고 성능도 좋지 않아 다음과 같이 바꿔주었습니다.

 

두번째 정답 코드

def solution(n, lost, reserve):
    answer = 0
    reserve.sort()
    temp = reserve[:]
    
    for i in reserve:
        if i in lost:
            lost.remove(i) 
            temp.remove(i)
    reserve = temp[:]
    
    for i in reserve:
        if lost:
            if i-1 in lost:
                lost.remove(i-1)
            elif i+1 in lost:
                lost.remove(i+1)
        else:
            break
            
    answer = n - len(lost)
    return answer

in을 사용해서 번호가 있는지 체크하고 정렬은 reserve만 했습니다.

 

결과 및 정리 

처음에 레벨 1 이라서 쉽게 생각했는데 은근 반례가 보이지 않아 헤맸습니다.

여벌의 체육복을 가진 학생은 도난 당한다는 조건을 읽지 못해 많이 헤맸습니다

reserve와 lost를 모두 정렬하지 않아서 그리디적으로 풀지 않았는데 조금 더 고민해보고 반례를 스스로 찾아가며 디버깅 해보겠습니다