[TIL] 그리디 알고리즘(탐욕법) / 프로그래머스 - 체육복

[Today I Learned]

#  그리디 알고리즘 (탐욕법)

- 현재 상황에서 지금 당장 좋은 것만 고르는 방법
- 단순히 가장 좋아 보이는 것을 반복적으로 선택해도 최적의 해를 구할 수 있는지 검토해야

- 일반적인 상황에서는 최적의 해를 보장할 수 없을 때가 많음
- 다만 코딩 테스트에서의 그리디 문제는 대부분 탐욕법으로 얻은 해가 최적의 해가 되는 상황에서, 이를 추론할 수 있어야 풀리도록 출제됨

ex. 거스름돈 문제

 

#  프로그래머스 - 체육복

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

점심시간에 도둑이 들어, 일부 학생이 체육복을 도난당했습니다. 다행히 여벌 체육복이 있는 학생이 이들에게 체육복을 빌려주려 합니다. 학생들의 번호는 체격 순으로 매겨져 있어, 바로 앞번호의 학생이나 바로 뒷번호의 학생에게만 체육복을 빌려줄 수 있습니다. 예를 들어, 4번 학생은 3번 학생이나 5번 학생에게만 체육복을 빌려줄 수 있습니다. 체육복이 없으면 수업을 들을 수 없기 때문에 체육복을 적절히 빌려 최대한 많은 학생이 체육수업을 들어야 합니다.

전체 학생의 수 n, 체육복을 도난당한 학생들의 번호가 담긴 배열 lost, 여벌의 체육복을 가져온 학생들의 번호가 담긴 배열 reserve가 매개변수로 주어질 때, 체육수업을 들을 수 있는 학생의 최댓값을 return 하도록 solution 함수를 작성해주세요.

 

@solution.py

answer = 0

# lost & reserve 중복 제거
_lost = [l for l in lost if l not in reserve]
_reserve = [r for r in reserve if r not in lost]

# 체육복 빌리기
for l in _lost:
    if (l-1) in _reserve:
        _lost.remove(l)
        _reserve.remove(l-1)
        
    elif (l+1) in _reserve:
        _lost.remove(l)
        _reserve.remove(l+1)

answer = n - len(_lost)

처음에 이렇게 코드를 구현했었는데 반복문을 돌고 있는 _lost의 원소를 remove하는 바람에, 두번째 루프부터 반복문이 제대로 동작하지 않았다.

 

def solution(n, lost, reserve):
    answer = 0

    # lost & reserve 중복 제거
    _lost = [l for l in lost if l not in reserve]
    _reserve = [r for r in reserve if r not in lost]
    
    _lost_tmp = _lost.copy()
    
    # 체육복 빌리기
    for l in _lost_tmp:
        if (l-1) in _reserve:
            _lost.remove(l)
            _reserve.remove(l-1)
            
        elif (l+1) in _reserve:
            _lost.remove(l)
            _reserve.remove(l+1)

    answer = n - len(_lost)
    
    return answer

그래서 for문을 돌리는 list를 copy하는 식으로 바꿨는데, 아직도 통과하지 못하는 2개의 케이스가 있었다.

 

def solution(n, lost, reserve):
    answer = 0

    # lost & reserve 중복 제거
    _lost = [l for l in lost if l not in reserve]
    _reserve = [r for r in reserve if r not in lost]
    
    _lost_tmp = sorted(_lost).copy()
    
    # 체육복 빌리기
    for l in _lost_tmp:
        if (l-1) in _reserve:
            _lost.remove(l)
            _reserve.remove(l-1)
            
        elif (l+1) in _reserve:
            _lost.remove(l)
            _reserve.remove(l+1)

    answer = n - len(_lost)
    
    return answer

문제는 바로 정렬..! 예시 케이스는 전부 번호가 sorting 된 상태로 주어져서 간과했던 부분이었다. sorted() 코드를 추가하고 나니 모든 테스트 케이스를 통과할 수 있었다.

 

이게 Level 1이라니 어렵자나,,! 😮