ProblemSolving/Greedy

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

OSNIM 2022. 5. 10. 19:11
반응형

Level 1 Greedy(탐욕법)

 

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

 

코딩테스트 연습 - 체육복

점심시간에 도둑이 들어, 일부 학생이 체육복을 도난당했습니다. 다행히 여벌 체육복이 있는 학생이 이들에게 체육복을 빌려주려 합니다. 학생들의 번호는 체격 순으로 매겨져 있어, 바로 앞번

programmers.co.kr

 

첫번째 정답 코드

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를 모두 정렬하지 않아서 그리디적으로 풀지 않았는데 조금 더 고민해보고 반례를 스스로 찾아가며 디버깅 해보겠습니다

반응형