알고리즘 - 체육복

문제 설명

점심시간에 도둑이 들어, 일부 학생이 체육복을 도난당했습니다. 다행히 여벌 체육복이 있는 학생이 이들에게 체육복을 빌려주려 합니다. 학생들의 번호는 체격 순으로 매겨져 있어, 바로 앞번호의 학생이나 바로 뒷번호의 학생에게만 체육복을 빌려줄 수 있습니다. 예를 들어, 4번 학생은 3번 학생이나 5번 학생에게만 체육복을 빌려줄 수 있습니다. 체육복이 없으면 수업을 들을 수 없기 때문에 체육복을 적절히 빌려 최대한 많은 학생이 체육수업을 들어야 합니다.

전체 학생의 수 n, 체육복을 도난당한 학생들의 번호가 담긴 배열 lost, 여벌의 체육복을 가져온 학생들의 번호가 담긴 배열 reserve가 매개변수로 주어질 때, 체육수업을 들을 수 있는 학생의 최댓값을 return 하도록 solution 함수를 작성해주세요.

제한사항

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

입출력 예

n lost reserve return
5 [2, 4] [1, 3, 5] 5
5 [2, 4] [3] 4
3 [3] [1] 2

입출력 예 설명

예제 #1
1번 학생이 2번 학생에게 체육복을 빌려주고, 3번 학생이나 5번 학생이 4번 학생에게 체육복을 빌려주면 학생 5명이 체육수업을 들을 수 있습니다.

예제 #2
3번 학생이 2번 학생이나 4번 학생에게 체육복을 빌려주면 학생 4명이 체육수업을 들을 수 있습니다.

문제 이해

• 처음엔 단순히 여분이 있는 학생목록을 루프로 돌면서
• 잃어버린 학생의 번호와 +-1 차이가 나는 값이 있다면
• 전체 학생에서 잃어버린 학생수를 뺀 값에 다시 빌린 학생수를 더해주면 되겠다 싶었다.

그러나 결과는 2개정도만 통과하고 참패

이유가뭘까 하고 다른사람들 질문도 찾아보고 했더니 테스트케이스에는 없는 간과하고 있던 부분이 있었다. 즉 잃어버린친구중에 여분이 있던 친구도 있는것 그렇다면 이 친구는 여분이 있던 친구지만 도난 당했기때문에 다른사람에 빌려줄수없다.

즉 이 문제는 잃어버린 배열과 여분이 있는 배열에서 중복되는 값을 제거하고 순수하게 잃어버린 친구들과 순수하게 빌려줄 여분을 갖고있는 친구들 목록을 가지고 코드를 작성해야한다.

sudo code

진짜 잃어버린 학생 = 잃어버린학생중 여분이 있는 친구목록에 포함되어있는 값을 제외한 배열
진짜 여분이 있는 학생 = 여분이 있는 학생중 도난당한 친구목록에 포함되어있는 값을 제외한 배열

잃어버린 친구들중에서 빌린 학생들 목록 = 진짜 잃어버린 학생들 중에서
  진짜 여분이 있는 학생들과 + 또는 - 1 차이나는 값이 있다면
  해당되는 값만 리턴

전체 학생 - (진짜 도난당한 학생 - 도난당한 학생들중 빌린학생)

Code

function solution(n, lost, reserve) {
    // 잃어버린 학생이 여분을 가진 학생일수도있는 중복값을 각각 제거한 새로운 배열 생성
    const realReserve = reserve.filter(r => !lost.includes(r));
    const realLost = lost.filter(r => !reserve.includes(r));

    // 진짜 잃어버린 학생들 중에서 여분을 갖고 있는 학생들에게 체육복을 빌리는 학생들의 배열을 리턴
    const result = realLost.filter(a => {
        return realReserve.find((b, i) => {
            const lend = b === a - 1 || b === a + 1;
            if (lend) {
                delete realReserve[i];
            }
            return lend;
        });
    });
    // 진짜 잃어버린 학생들에서 다시 체육복을 빌린 학생수를 빼고 그 값을 전체 학생수에서 뺀다
    return n - (realLost.length - result.length);
}

그리디(탐욕법) 알고리즘

그리디 알고리즘이란 매 선택에서 지금 이순간 가장 최적인 답을 선택하여 적절한 결과를 도출하자 라는 알고리즘 설계 기법이다.

위 문제를 그리디 알고리즘으로 풀이하자면 체육복에 여분이 있는 학생은 자신의 +1 또는 -1 의 학생에게만 체육복을 빌려 줄 수있다. 바로옆에 있는 학생에 체육복을 빌려줄 수 있는건 현재 가장 최적의 선택방법이겠지만 만약 여분이 있는데 앞 뒤에 아무도 없고 2번째 혹은 3번째에 체육복이 없는 친구가 있다면

여분이 있어도 현실적으로는 빌려줄수있어도 그리디 알고리즘에서는 빌려줄 수가 없다. 현재에서 가장 최적의 답을 선택하는 알고리즘 이지만 전체적으로봤을때는 최적의 상황이 아닐 수 있다 라는것이 포인트이다.