탐욕법(Greedy) 대표 문제 풀이: 체육복

문제 링크 : https://school.programmers.co.kr/learn/courses/30/lessons/42862

프로그래머스

---

탐욕법(Greedy Algorithm)

• 알고리즘의 각 단계에서 그 순간에 최적이라고 생각되는 것을 선택
• (탐욕법으로 최적해를 찾을 수 있는 문제) 현재의 선택이 마지막 해답의 최적성을 해치지 않을 때

• 이 문제에서는 빌려줄 학생들을 "정해진 순서"로 살펴야 하고,
• 이 "정해진 순서"에 따라
• 우선하여 빌려줄 방향을 정해야 함

문제의 해결 - 방법(1)

• (착안점) 학생의 범위가 굉장히 좁으므로
• 학생 수만큼 배열을 확보하고, 여기에 각자가 가지고 있는 체육복의 수를 기록한다. -> 번호 순서대로 스캔하면서 빌려줄 관계를 정한다.

def solution(n, lost, reserve):
    uniform = [1] * (n + 2)
    for i in reserve:
        uniform[i] += 1
    for i in lost:
        uniform[i] -= 1

    for i in range(1, n+1):
        if uniform[i-1] == 0 and uniform[i] == 2:
            uniform[i-1:i+1] = [1, 1]
        elif uniform[i] == 2 and uniform[i+1] == 0:
            uniform[i:i+2] = [1, 1]

    return len([x for x in uniform[1:-1] if x > 0])

📌 지금 해결 방법의 시간 복잡도는 $O(n)$ 이다.

그런데 만약 전체 학생 수가 매우 크다면? -> 문제의 성질상 위 시간복잡도보다 낮은 알고리즘 설계는 힘들것 같다.

📌 그런데 만약 여벌의 체육복을 가져온 학생수가 매우 적다면?

• 여벌의 체육복을 가져온 학생들의 번호(reserve)를 정렬하고,
• 이것을 하나 하나 순서대로 살펴보면서
• 빌려줄 수 있는 다른 학생을 찾아서(해시를 적용해서 상수 시간에 처리) 처리한다 ($O(k\log k)$)
  • 여벌이 있는 학생 k, 전체 학생수는 n
  • 여벌이 있는 학생이 매우 적다고 가정했으므로 $k\log k < n$

def solution(n, lost, reserve):
    s = set(lost) & set(reserve)
    l = set(lost) - s
    r = set(reserve) - s
    for x in sorted(r):
        if x - 1 in l:
            l.remove(x - 1)
        elif x + 1 in l:
            l.remove(x + 1)
    return n - len(l)