체육복

문제

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

접근

• 그리디 문제는 현재 선택 가능한 최적의 방법으로 문제를 해결하면 된다. 체육복을 들고 오지 않은 학생의 번호가 담긴 배열 lost 에서 하나씩 순회하며 여분의 체육복을 가져온 학생 번호가 담긴 reserve 배열을 순회하는 방식으로 접근했다.
• 자료구조는 키-값쌍이 따로 필요한 문제는 아닌것처럼 보여 배열을 사용했다.

코드

function solution(n, lost, reserve) {
    var answer = 0;
    let recover=0;

    // 도난당한 학생이 여벌이 있는 경우 제거
    let realLost = lost.filter(l => !reserve.includes(l)); //필터
    let realReserve = reserve.filter(r => !lost.includes(r)); // 필터

    realLost.sort((a,b) => a-b); //정렬
    realReserve.sort((a,b) => a-b); //정렬

    for(let i = 0 ; i < realLost.length ; i++){ // 이중반복문을 통해 체육복 빌려주기
        for(let j = 0 ; j < realReserve.length ; j++){
            if(Math.abs(realLost[i] - realReserve[j]) <= 1){
                realReserve[j] = -1; // 빌려줬음을 표시
                recover++;
                break;
            }
        }
    }
    answer = n - realLost.length + recover;
    return answer;
}

코드 설명

필터

• 체육복을 도난 당했지만 여분의 체육복을 가져온 학생은 다른 학생에게 체육복을 빌려줄 수 없다는 조건이 있으므로 도난당한 학생이 여벌이 있는 경우를 제거한다.

정렬

• realLost와 realReserve 배열을 오름차순으로 정렬한다. 이로 인해, 체육복을 빌려주는 로직이 간단해진다.

이중 반복문을 통한 체육복 빌려주기

• realLost 배열을 순회하며, 각 도난당한 학생이 여벌 체육복을 가진 학생에게 빌릴 수 있는지 확인한다.
• Math.abs(realLost[i] - realReserve[j]) <= 1 조건을 사용해, 체육복을 빌릴 수 있는지 확인한다. realLost[i]가 realReserve[j]와 바로 인접한 학생일 때만 체육복을 빌릴 수 있다.
• 체육복을 빌려준 후에는 realReserve[j] 값을 -1로 설정하여 해당 학생이 이미 체육복을 빌려준 상태임을 표시한다.
• 체육복을 빌린 경우 recover 값을 1 증가시킨다.

최종 결과 계산

• n - realLost.length + recover로 체육 수업에 참여할 수 있는 학생 수를 계산하여 answer 변수에 저장하고, 이를 반환한다.

해설 1에 대한 시간복잡도 분석

필터링:

• lost와 reserve 배열을 각각 필터링하는 과정에서 두 배열을 비교한다.
• 시간 복잡도: O(l * r) (l은 lost의 길이, r은 reserve의 길이)

정렬:

• realLost와 realReserve 배열을 각각 정렬한다.
• 시간 복잡도: O(l * log(l)) 및 O(r * log(r))

이중 반복문:

• realLost배열의 각 요소에 대해 realReserve 배열을 순회하며 체육복을 빌려주는 과정이다.
• 시간 복잡도: O(l * r)

전체 시간 복잡도 ⇒ O(l * r + l * log(l) + r * log(r) + l * r) ⇒ 최악의 경우 O(l*r)

최적화를 해봅시다.

효율적인 자료구조와 이중 반복문을 없앨 수 있는 방법을 생각해보자. 일단 이중 반복문을 없애는 것이 최우선과제이다. 문제를 다시보면 병합정렬과 비슷하다는 것을 볼 수 있다.

function solution(n, lost, reserve) {
    // 도난당한 학생이 여벌이 있는 경우 제거
    let realLost = lost.filter(l => !reserve.includes(l));
    let realReserve = reserve.filter(r => !lost.includes(r));

    // 배열 정렬
    realLost.sort((a, b) => a - b);
    realReserve.sort((a, b) => a - b);

    let recover = 0;
    let i = 0;
    let j = 0;

    while(realLost.length!==i && realReserve.length!==j){
        if(Math.abs(realLost[i]-realReserve[j])===1){
            i++;
            j++;
            recover++;
        }else if(realLost[i]>realReserve[j]){
            j++;
        }else if(realLost[i]<realReserve[j]){
            i++;
        }
    }
    return n - realLost.length + recover;
}

코드 설명

중복 제거:

• lost 배열에서 여벌의 체육복이 있는 학생(reserve 배열에 포함된 학생)을 제외하고 realLost 배열에 저장한다.
• 마찬가지로, 여벌의 체육복을 가진 학생 중 체육복을 도난당한 경우를 제외하고 realReserve 배열에 저장한다.

정렬:

• realLost와 realReserve 배열을 오름차순으로 정렬한다. 이는 이후 체육복을 빌려줄 때, 인접한 학생들부터 우선적으로 처리하기 위함이다.

체육복 대여:

• 두 포인터 i와 j를 사용하여 realLost와 realReserve 배열을 순회한다.
• 만약 realLost[i]와 realReserve[j]의 차이가 1이라면 (Math.abs(realLost[i]-realReserve[j])===1) , realReserve[j] 학생이 realLost[i] 학생에게 체육복을 빌려줄 수 있다는 의미이므로, recover를 증가시키고 두 포인터를 모두 증가시킨다.
• 만약 realLost[i]가 realReserve[j]보다 크다면, realReserve[j]를 다음 학생으로 이동시키기 위해 j++ 한다.
• 반대로 realLost[i]가 realReserve[j]보다 작다면, realLost[i]를 다음 학생으로 이동시키기 위해 i++ 한다.

결과 계산:

• 전체 학생 수 n에서 체육복을 잃어버린 학생 수(realLost.length)를 빼고, 그중 체육복을 빌린 학생 수(recover)를 더해 최종적으로 체육복을 가진 총 학생 수를 반환한다.

시간 복잡도 분석

중복 제거 (filter):

• filter 함수는 각 배열을 순회하며, 각 배열의 길이에 비례한 시간복잡도를 갖는다. 따라서 이 단계의 시간복잡도는 O(n)이다.

정렬:

• realLost와 realReserve 배열을 정렬하는 데 걸리는 시간은 각각 O(L log L)과 O(R log R)이다. 여기서 L은 realLost 배열의 길이, R은 realReserve 배열의 길이이다. 하지만 두 배열의 길이는 최악의 경우에도 n보다 작으므로, 정렬 단계의 시간복잡도는 O(n log n)으로 볼 수 있다.

체육복 대여:

• 두 포인터 i와 j를 사용하여 realLost와 realReserve 배열을 순회하는데, 이 과정에서 각 포인터는 배열의 길이만큼 최대 한 번씩 증가하므로, 이 단계의 시간복잡도는 O(n)이다.

결론적으로, 이 함수의 전체 시간복잡도는 O(n log n)이다. 이는 주로 배열을 정렬하는 데 소요되는 시간이 지배적이기 때문이다.

⇒ 시간 복잡도를 줄이는데 성공했다.

교훈

• 그리디 문제는 부분적인 상황에 대한 최적해의 모음이므로 정렬과 연관된 경우가 많다.
• 이중반복문을 사용했다면 그곳에서 최적화를 시도해보자.
• 그리디는 부분적 상황에 대한 최적해이므로 반복문 사용시 횟수를 미리 생각하기 힘든 경우가 많다. 그럴 때, While(C ≠ ∅ AND not Solution(S)) // Solution집합이 아직 해결책이 아니고 Candidate집합이 공집합이 아닐 경우 를 생각해서 while 문을 사용해보자.