[프로그래머스] '22.11.22. Training Clothes

n = 5

reserve = [1,3,5]

lost = [2,4]

 

1 3 5 -> 1 3 번이 2 4에게 또는 3 5 번이 2 4에게 줄 수 있음

  2 4

 

탐욕법 (Greedy Algorithm)

1. 알고리즘의 각 단계에서 그 순간에 최적이라고 생각되는 것을 선택

2. 탐욕법으로 최적해를 찾을 수 있는 문제 -> 현재 선택이 마지막까지 최고의 선택일 경우 가능

 

탐욕법 적용 가능성 확인

2 4 6 만약 2번이 3, 4번이 5 빌려줄 경우? -> 2 3 4 5 6 만 받을 수 있으므로 정답이 아님

1 3 5

 

따라서 빌려줄 학생들을 "정해진 순서"로 살펴야 하고,

이 "정해진 순서"에 따라 우선하여 빌려줄 방향을 정해야함.

 

Solution(1)

학생의 수는 기껏해야 30명 -> 학생 수만큼 배열을 확보하고,

여기에 각자가 가지고 있는 체육복의 수를 기록함

-> 번호 순서대로 "Scan"하면서 빌려줄 관계를 정함.

 

여벌을 가져온 학생 처리 : reserve의 길이에 비례

체육복을 잃어버린 학생 처리 : lost의 길이에 비례

체육복 빌려주기 처리 : 전체 학생 수 (n)에 비례 -> O(n)

 

Solution(2)

만약 전체 학생 수가 매우 크다면?

but -> 문제의 성질상 O(n)보다 낮은 복잡도 알고리즘은 어려움

 

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

 

여벌의 체육복을 가져온 학생들의 번호(reserve)를 정렬하고,

이것을 하나 하나 순서대로 살펴보면서

빌려줄 수 있는 다른 학생을 찾아서 처리한다!

-> Hash를 적욯해서 상수 시간내 처리

-> O(k) * O(1) // 여벌을 가져왔지만, 잃어버린 경우도 처리해야 하므로

 

번호를 정렬할 경우 reserve = k개인 경우 O(klogk) -- N > k가 많이 작을 경우