[알고리즘]- 체육복

풀이 시간 : 56분 09초

핵심 포인트
1. 중복 제거 : 도난당한 학생과 여분을 가진 학생의 중복을 제거하는 것이 중요
2. 정렬 : 학생들의 번호가 정렬된다는 조건이 없으므로, 해당 사항 고려 필요

추가로 배운점
1. 그리디 알고리즘 
2. delete 사용법
3. filter 오브젝트를 만들어서 로직을 간결하게 작성하는 방식
4. 앞뒤숫자 탐색을 abs 를 활용해서 처리하는 방식

문제 설명

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

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

제한사항

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

풀이

function solution(n, lost, reserve) {
    // 체육복을 잃어버렷지만 여분의 체육복이 있는 경우 제외
    // 오름차순으로 정렬 안할시 반례가 생김
    let realLost = lost.filter(v => !reserve.includes(v)).sort((a, b) => a - b);
    let realReserve = reserve.filter(v => !lost.includes(v)).sort((a, b) => a - b);
    
    for (const student of realLost){
        const posGo = student - 1;
        const posBack = student + 1;
        
        if(realReserve.includes(posGo)){ // 앞번호에서 빌리는 경우 
            realReserve = realReserve.filter(v => v !== posGo);
        }else if(realReserve.includes(posBack)){ // 뒷번호한테 빌리는 경우
            realReserve = realReserve.filter(v => v !== posBack);
        }else{ // 빌리지 못한 경우
            n--;
        }
    }
    
    return n;
}
// 반례 case 13 
// 입력값 〉 5, [4, 2], [3, 5]
// 기댓값 〉 5

// want
// n 명의 학생중, lost 는 체육복을 가져오지 않은 학생 , reserve 는 여분의 체육복을 가져온 학생
// 조건 1. reserve 학생은 자신의 앞뒤번호의 학생에게만 체육복을 빌려 줄 수 잇음
// 조건 2. 체육복은 1개만 빌릴 수 있음 
// 체육수업을 들을 수 있는 학생의 최대값을 반환함

// solving
// 1. 체육복을 잃어버렸는데, 여분을 가지고 있는 경우
// 2. 앞번호에서 빌리는 경우 제외
// 3. 뒷번호에서 빌리는 경우 제외

해당 문제는 크게 체육복을 잃어버렸지만 여분의 체육복을 가진 학생을 제거, 학생들 번호가 순차적으로 정렬되었는지 2개의 문제가 중요했습니다.

다른 사람 풀이

/**
 * n: 전체 학생 수
 * lost: 체육복을 도난당한 학생들의 번호
 * reserve: 여벌의 체육복을 가져온 학생들의 번호
 *
 * 목표: 체육복을 빌려 최대한 많은 학생이 체육 수업을 듣는 것
 *
 * 결정의 순간마다 최적의 상황만을 쫓아 최적의 해에 도달하는 기법
 * - 선택 절차: 현재 상태에서의 최적의 해답을 선택한다.
 * - 적절성 검사: 선택된 해가 문제의 조건을 만족하는지 검사한다.
 * - 해답 검사: 원래의 문제가 해결되었는지 검사하고, 해결되지 않았다면 1번으로 돌아가 과정을 반복한다.
 *
 * n = 5;
 * lost = [2, 4];
 * reserve = [3];
 *
 * 일단 reserve에서 lost에 있는 것을 빼야한다. => uLost, uReserve
 * uReserve의 탐색을 빠르게 하기 위해 Set으로 한다.
 * result에 최댓값을 저장하기 위해 n - uLost.length로 설정한다.
 */
function solution(n, lost, reserve) {
  const uLost = lost.filter((item) => !reserve.includes(item));
  const uReserve = new Set(reserve.filter((item) => !lost.includes(item)));
  let result = n - uLost.length;
  uLost.forEach((lostItem) => {
    if (uReserve.has(lostItem - 1)) {
      uReserve.delete(lostItem - 1);
      result += 1;
    } else if (uReserve.has(lostItem + 1)) {
      uReserve.delete(lostItem + 1);
      result += 1;
    }
  });
  return result;
}

주석으로 문제를 정리하는 방식, 그리디 알고리즘, delete 사용법 등 배울점이 있어 정리했습니다.

function lostFilter(lost, reserve, findT) {
  const filterT = { me: true, friend: false };

  return lost.filter(lostN => {
    const existI = reserve.findIndex(reserveN => filterT[findT]
                                               ? reserveN === lostN
                                               : Math.abs(reserveN - lostN) <= 1);
    if(existI === -1) return true;
    reserve.splice(existI, 1);
  });
}

function solution(n, lost, reserve) {
  const selfLost = lostFilter(lost,     reserve, 'me'    );
  const realLost = lostFilter(selfLost, reserve, 'friend');

  return n - realLost.length;
}

filterT 를 사용해서 검색을 효율적으로 짜는 방식과 앞뒤 숫자 탐색을 Math.abs() 를 활용하는 방식등 배울점이 많아 가져왔습니다.