99클럽(2기) - 코테스터디 9일차 TIL # Greedy

프로그래머스 - 체육복

문제

점심시간에 도둑이 들어, 일부 학생이 체육복을 도난당했습니다. 다행히 여벌 체육복이 있는 학생이 이들에게 체육복을 빌려주려 합니다. 학생들의 번호는 체격 순으로 매겨져 있어, 바로 앞번호의 학생이나 바로 뒷번호의 학생에게만 체육복을 빌려줄 수 있습니다. 예를 들어, 4번 학생은 3번 학생이나 5번 학생에게만 체육복을 빌려줄 수 있습니다. 체육복이 없으면 수업을 들을 수 없기 때문에 체육복을 적절히 빌려 최대한 많은 학생이 체육수업을 들어야 합니다. 전체 학생의 수 n, 체육복을 도난당한 학생들의 번호가 담긴 배열 lost, 여벌의 체육복을 가져온 학생들의 번호가 담긴 배열 reserve가 매개변수로 주어질 때, 체육수업을 들을 수 있는 학생의 최댓값을 return 하도록 solution 함수를 작성해주세요.

 

제한사항

• 전체 학생의 수는 2명 이상 30명 이하입니다.
• 체육복을 도난당한 학생의 수는 1명 이상 n명 이하이고 중복되는 번호는 없습니다.
• 여벌의 체육복을 가져온 학생의 수는 1명 이상 n명 이하이고 중복되는 번호는 없습니다.
• 여벌 체육복이 있는 학생만 다른 학생에게 체육복을 빌려줄 수 있습니다.
• 여벌 체육복을 가져온 학생이 체육복을 도난당했을 수 있습니다. 이때 이 학생은 체육복을 하나만 도난당했다고 가정하며, 남은 체육복이 하나이기에 다른 학생에게는 체육복을 빌려줄 수 없습니다.

---

1. 나의 풀이

1) 여벌 체육복을 가지고 왔지만 도난당한 학생은 데이터셋에서 제거

 lost와 reserve에 모두 존재하는 학생을 제거하고 시작하는 것이 문제를 더 쉽게 푸는 방법이라고 생각했다. 여벌 체육복을 가져왔지만 도난당한 경우 체육복을 빌릴 필요도, 빌려줄 수도 없기 때문이다. 따라서 lost와 reserve를 set 자료형으로 형변환해주고 교집합을 구해 lost, reserve에서 각각 제거해줬다.  

 

2) 여벌 체육복을 가진 학생 앞 뒤에 체육복을 잃어버린 학생이 있다면 빌려주기

 여벌 체육복을 가진 학생의 앞 번호를 먼저 체크해서 있으면 빌려주고 없으면 뒷 번호를 체크해서 빌려준다.  

 

3) 전체 학생 수에서 아직도 체육복을 빌리지 못 한 학생 수를 빼서 반환

 기존에 체육 수업을 들을 수 있는 인원은 n에서 lost를 뺀 수였다. 그런데 2)의 작업을 통해 lost_set에서 체육복을 빌린 학생은 제외되었으므로 n에서 lost_set 수를 빼면 체육복을 빌렸든 기존에 가지고 있든 체육복을 입고 체육 수업을 들을 수 있는 학생 수가 나온다.  

def solution(n, lost, reserve):

    # 여벌 체육복을 가지고 왔지만 도난당한 학생은 데이터셋에서 제외
    lost_set = set(lost)
    reserve_set = set(reserve)
    both = lost_set & lost_reserve
    lost_set -= both
    reserve_set -= both
    
    # 여벌 체육복을 가진 학생 앞, 뒤로 체육복이 없는 학생이 있다면 빌려주기
    for r in sorted(reserve_set): # 오름차순으로 정렬되어있지 않았을 경우를 대비해서 정렬
        if (r - 1) in sorted(lost_set):
            lost_set.remove(r - 1) # r - 1에게 빌렸다면 체육복 없는 학생 목록에서 r - 1 제거
        elif (r + 1) in sorted(lost_set):
            lost_set.remove(r + 1) # r + 1에게 빌렸다면 체육복 없는 학생 목록에서 r + 1 제거
    
    # 아직도 못 빌려서 체육복이 없는 학생 수를 제외한 학생 수 반환
    return n - lost_set

 

 

2. 다른 사람의 풀이

 투 포인터로 풀이한 분이 계셨다. 오.. 이런 생각도 할 수가 있구나..! 나의 방법보다 확실히 순회를 덜 할 수 있다. 내 풀이에서 최악의 경우 여벌의 체육복이 있는 학생이 반에서 맨 뒷 번호를 가졌다면, 빌려야 하는 학생을 찾기 위해서 마지막 앞 번호까지 순회를 해야하지만, 이 풀이에서는 최악의 경우에도 min(여벌의 체육복이 있는 학생 수, 빌려야하는 학생 수)의 범위에서만 순회하면 된다. 하지만 O(0.xn)의 시간 복잡도를 갖는다고 하더라도 상수는 의미 없으므로 결과적인 시간복잡도는 나의 풀이와 동일하게 O(n)이다. 또한 풀이 방식은 좀 더 복잡하다는 생각이 든다. 

def solution(n, lost, reserve):
    l = len(lost)
    r = len(reserve)
    lost.sort()
    reserve.sort()
    answer = n - l
    pl = 0  # lost의 인덱스
    pr = 0  # reserver의 인덱스
    while pl < l and pr < r:  # 파라미터 2개로 투포인터 비스무리하게 greedy 풀이 진행
        if -1 <= lost[pl] - reserve[pr] <= 1:  # 빌려줄수있는경우
            answer += 1
            if lost[pl] > reserve[pr] and pr + 1 < r and reserve[pr + 1] == lost[pl]:
                # 근데 빌려줄 사람이 본인체육복을 도난당한경우 다른사람 못빌려주므로 뒷사람 못빌려줌
                pr += 2
                pl += 1
            elif lost[pl] < reserve[pr] and pl + 1 < l and reserve[pr] == lost[pl + 1]:
            	# 마찬가지로 앞사람 못빌려주는경우
                pl += 2
                pr += 1
            else:
                pl += 1
                pr += 1
        elif lost[pl] > reserve[pr]:  # 못빌려주는경우
            pr += 1
        else:  # 못빌려주는경우2
            pl += 1
    return answer

 

 

3. 새로 알게된 점 & 정리

《Introduction to Algorithms》에 따르면 '탐욕적'이라는 의미의 그리디 알고리즘은 지금 당장 최적으로 보이는 선택을 반복해서 최적에 근접한 답을 도출하는 방법이라고 한다. 이는 지역적으로 최적인 선택이 모였다고 해서 전역적으로 최적인 선택이 보장되는 것은 아니지만 근사치에는 도달할 수 있음을 전제로 한다. 그리디 알고리즘이 잘 작동하려면 이전의 선택이 이후의 선택에 영향을 주지 않는다는 탐욕스러운 선택 속성(greedy choice property) 조건과, 전역적 최적해가 지역적 최적해와 일치한다는 최적 부분 구조(optimal substructure) 조건을 만족해야 한다.

 

 내 풀이에서는 체육복이 없는 학생 목록과 여벌이 있는 학생 목록을 오름차순으로 정렬하고, 체육복이 없는 학생이 여벌이 있는 학생에게 빌렸다면 lost_set에서 제거함으로써 이후의 선택에 영향을 안 주도록했다. 이는 '탐욕스러운 선택 속성' 조건을 만족시킨다. 또한, 여벌 체육복을 가진 학생의 앞 번호를 먼저 체크해서 있으면 빌려주고 없으면 뒷 번호를 체크하는 방식으로 당장의 최적 조건을 만족시켰고, 이 과정을 반복해서 전체의 최적해를 구했다.

 

 만약 여벌 체육복을 가진 학생의 앞, 뒤 학생에게만 체육복을 빌려줄 수 있다는 조건이 없었다면 부분적인 선택이 전체의 선택에 미치는 영향은 빌려줄 수 있는 대상의 범위만큼 커져서 그리디 알고리즘으로 문제를 풀이할 수 없었을 것이다. 물론 앞, 뒤 중 선택하는 과정에서도 최적이 아닐 가능성이 생길 수 있을 것 같은데, 이 부분에 대해서는 조금 더 고민해봐야할 것 같다. 

 

 

4. 참고 

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

탐욕 알고리즘 - 위키백과, 우리 모두의 백과사전

https://adjh54.tistory.com/212#1.%20%ED%83%90%EC%9A%95%20%EC%84%A0%ED%83%9D%20%EC%86%8D%EC%84%B1(Greedy%20Choice%20Property)-1

[Java/알고리즘] 그리디 알고리즘(탐욕법, Greedy Algorithm) 이해하기