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

---

문제분석

문제설명

제한사항

입출력 예

필요 개념

탐욕법(Greedy)

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

탐욕법 적용 가능성 확인

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

---

python 언어를 이용한 풀이

배열을 이용한 풀이

착안점

• 학생의수는 30명으로 소수 이므로, 학생 수 만큼 배열을 확보하고, 여기에 각자가 가지고 있는 체육복의 수를 기록한다.
• 번호 순서대로 스캔 하면서 빌려줄 관계를 정한다.

코드

def solution(n, lost, reserve):
    uniform = [1] * (n + 2)
    
    for i in lost:
        uniform[i] -= 1
    for i in reserve:
        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]
            
        if uniform[i + 1] == 0 and uniform[i] == 2:
            uniform[i:i + 2] = [1, 1]
    
    return len([x for x in uniform[1:-1] if x>0])

알고리즘의 복잡도

여벌을 가져온 학생 처리 : reserve 의 길이에 비례
체육복을 잃어버린 학생 처리 : lost의 길이에 비례
체육복 빌려주기 처리 : 전체 학생수 N에 비례

• 최종 시간 복잡도 : O(N)

정렬(sort)을 이용한 풀이

착안점

• 만약 전체 학생수가 매우 크다면?
  • 문제의 성질상 O(N)보다 낮은 복잡도 알고리즘을 어려울 것
• 더하여 여별의 체육복을 가져온 학생을 매우 적다면?
  • 여벌의 체육복을 가져온 학생들의 번호(reserve)를 정렬하고,
    이것을 순서대로 살펴보면서 빌려줄수 있는 다른 학생을 찾아서 처리한다.

• 정렬을 이용하므로 시간 복잡도는 O(klogk)
• 해시를 적용해서 상수 시간에 처리

코드

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

알고리즘의 복잡도

여벌의 체육복을 가져온 학생들의 번호(reserve)를 정렬
-> O(klogk)
체육복을 빌려줄 수 있는 학생을 찾아 처리
-> O(k) * O(1)
전체 알고리즘의 시간 복잡도
-> O(klogs)

---