체육복

문제풀이

def solution(n, lost, reserve):
    
    #잃어버린 학생 중 여벌을 가지고 있는 학생 제외
    for lost_st in lost[:]:
        if lost_st in reserve:
            del reserve[reserve.index(lost_st)]
            del lost[lost.index(lost_st)]
    
    lost.sort()
    reserve.sort()
    
    for lost_st in lost[:]:
         for reserve_st in reserve[:]:
                if lost_st - 1 == reserve_st or lost_st + 1 == reserve_st:
                    del reserve[reserve.index(reserve_st)]
                    del lost[lost.index(lost_st)]
                    break
            
    answer = n - len(lost)
    
    return answer

알고리즘

탐욕법(Greedy)

이 문제의 핵심은 누가 누구에게 빌려주었든 간에 답에는 영향을 끼치지 않는다는 것이다.

나의 코드를 보면 잃어버린 사람 중 자기 여부를 가지고 있는 사람은 다른 사람에게 빌려줄 수 없다고 해서 이 부분을 먼저 처리한 뒤 타인에게 빌려줄 수 있는 경우를 계산한다. 하지만 이 과정(자기 자신에게 여분을 채우는 과정)을 하지 않고 바로 후자인 부분으로 처리해도 큰 문제는 없을 것이다. (다만 자기 자신과 같은 번호일 경우를 추가해야 할 것이다.)

 

탐욕 알고리즘은 여러 경우 중 하나를 결정해야 할 때마다 그 순간에 최적이라고 생각되는 것을 선택해 나가는 방식으로 진행하여 최종적인 해답에 도달한다. 즉, 지역적으로 최적이면서 전역적으로 최적인 문제일 경우이다.

 

탐욕 알고리즘이 잘 작동하는 문제는 대부분 탐욕스러운 선택 조건(greedy choice property)과 최적 부분 구조 조건(optimal substructure)이라는 두 가지 조건이 만족된다. 탐욕스런 선택 조건은 앞의 선택이 이후의 선택에 영향을 주지 않는다는 것이며, 최적 부분 구조 조건은 문제에 대한 최적해가 부분 문제에 대해서도 역시 최적해라는 것이다.

출처

문제: 프로그래머스 코딩 테스트 연습, https://programmers.co.kr/learn/challenges

코딩테스트 연습

탐욕 알고리즘: https://ko.wikipedia.org/wiki/%ED%83%90%EC%9A%95_%EC%95%8C%EA%B3%A0%EB%A6%AC%EC%A6%98