체육복

문제 설명

점심시간에 도둑이 들어, 일부 학생이 체육복을 도난당했습니다. 다행히 여벌 체육복이 있는 학생이 이들에게 체육복을 빌려주려 합니다. 학생들의 번호는 체격 순으로 매겨져 있어, 바로 앞번호의 학생이나 바로 뒷번호의 학생에게만 체육복을 빌려줄 수 있습니다. 예를 들어, 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명이 체육수업을 들을 수 있습니다.

해결

function isValid(LS, RS) {
  // LS = Lost Students
  // RS = Reserve Student
  for (let i = 0; i < LS.length; i++) {
    let downNumber = RS - 1;
    let upNumber = RS + 1;
    if (LS[i] === downNumber) {
      return LS[i];
    } else if (LS[i] === upNumber) {
      return LS[i];
    }
  }
  return false; // basic result
}

function isReserveLost(LS, RS) {
  // LS = Lost Students
  // RS = Reserve Student
  // 만약에 checkDifference의 값이 LS의 길이와 다르다면 빌려주는 학생의 배열과
  // 잃어버린 학생의 배열에 같은 값이 들어가 있다는 뜻.
  // 도둑이 여분의 체육복을 가져온 학생의 옷을 가져갔다는 의미.
  const checkDifference = LS.filter((item) => item !== RS).length;
  return checkDifference === LS.length;
}

function solution(n, lost, reserve) {
  // 만약 주어진 매개 변수들이 5, [4,2], [3,5]이라면
  // 빌려주는 학생 3은 2를 빌려주고 학생 5는 4를 빌려주는게 가장 많은 학생이 수업을 들을 수 있는
  // 방법이다. 만약에 정렬을 하지 않는다면, 로직의 순서상 학생 3은 4번 학생에게 옷을 빌려주게 되고,
  // 2번 학생은 5번 학생과 옷의 사이즈가 맞지 않기 때문에 총 4명만이 수업을 들을 수 있다.
  // 이러한 경우를 배제하기 위해서 들어오는 배열을 순서대로 정렬할 필요가 있다.
  lost = lost.sort((a, b) => a - b);
  reserve = reserve.sort((a, b) => a - b);

  // 여벌이 있는 학생이 도난 당했을 경우 체크
  for (let i = 0; i < reserve.length; i++) {
    if (!isReserveLost(lost, reserve[i])) {
      lost = lost.filter((item) => item !== reserve[i]);
      reserve = reserve.filter((item) => item !== reserve[i]);
      i--;
    }
  }

  // 여벌이 있는 학생 중 위 아래로 번호가 있는지 체크.
  for (let i = 0; i < reserve.length; i++) {
    if (isValid(lost, reserve[i])) {
      lost = lost.filter((item) => item !== isValid(lost, reserve[i]));
    }
  }
  const resultReserve = n - lost.length;
  return resultReserve;
}

문제는 그리디로 해결하는 문제였지만, 그리디 알고리즘에 대한 이해도가 부족해서 여러가지 방법을 시도해봤습니다! 위의 해결법은 두 가지의 함수를 사용해서 이뤄져있습니다.

우선 여분의 옷을 가져온 학생의 옷이 도둑질 당했을 경우를 처리하기 위해서 isReservedLost 라는 함수를 만들어봤습니다. 이 함수는 체육복을 잃어버린 학생들의 번호가 담겨있는 lost라는 배열에 여분의 옷이 있는 학생의 번호를 하나씩 넣어봐서 lost함수에 여분의 옷이 있는 학생의 번호가 있는지 체크하는 함수입니다.

두 번째 함수는 isValid라는 함수입니다. 여분의 옷이 있다고 하더라도 자신의 번호에서 위 아래 한 칸의 차이가 있는 학생들만이 옷을 빌릴 수 있기 때문에, 그 과정을 체크하는 함수입니다. isValid가 true가 나온다면, 체육복을 잃어버린 학생들의 배열 lost에서 옷을 받은 학생의 번호를 제거하는 식으로 구성해봤습니다.

최후에는 빌려준 결과라는 변수를 만들어서 총 학생의 수에서 체육복을 잃어버린 학생들의 배열의 총 길이를 빼줘서 체육 시간에 참여할 수 있는 학생의 수를 리턴해줍니다.

이 다음 방법은 재귀 함수와 이진탐색을 연습하기 위해 작성해봤습니다.

재귀 함수와 이진탐색 연습용

function isValid(LS, RS) {
    // LS = Lost Students
    // RS = Reserve Student
    for (let i = 0; i < LS.length; i++) {
      let downNumber = RS - 1;
      let upNumber = RS + 1;
      if (LS[i] === downNumber) {
        return LS[i];
      } else if (LS[i] === upNumber) {
        return LS[i];
      }
    }
    return false; // basic result
  }

  function isReserveLost(LS, RS) {
    // LS = Lost Students
    // RS = Reserve Student
    // 재귀함수를 이용한 이진 탐색 알고리즘 사용.
    if (LS.length === 0) {
      return false;
    }
    const halfLS = Math.floor(LS.length / 2);
    if (RS < LS[halfLS]) {
      const newLS = LS.slice(0, halfLS);
      return isReserveLost(newLS, RS);
    } else if (RS > LS[halfLS]) {
      const newLS = LS.slice(halfLS + 1);
      return isReserveLost(newLS, RS);
    } else {
      return true;
    }
  }

  function solution(n, lost, reserve) {
    // 만약 주어진 매개 변수들이 5, [4,2], [3,5]이라면
    // 빌려주는 학생 3은 2를 빌려주고 학생 5는 4를 빌려주는게 가장 많은 학생이 수업을 들을 수 있는
    // 방법이다. 만약에 정렬을 하지 않는다면, 로직의 순서상 학생 3은 4번 학생에게 옷을 빌려주게 되고,
    // 2번 학생은 5번 학생과 옷의 사이즈가 맞지 않기 때문에 총 4명만이 수업을 들을 수 있다.
    // 이러한 경우를 배제하기 위해서 들어오는 배열을 순서대로 정렬할 필요가 있다.
    lost = lost.sort((a, b) => a - b);
    reserve = reserve.sort((a, b) => a - b);

    // 여벌이 있는 학생이 도난 당했을 경우 체크
    for (let i = 0; i < reserve.length; i++) {
      if (isReserveLost(lost, reserve[i])) {
        lost = lost.filter((item) => item !== reserve[i]);
        reserve = reserve.filter((item) => item !== reserve[i]);
        i--;
      }
    }

    // 여벌이 있는 학생 중 위 아래로 번호가 있는지 체크.
    for (let i = 0; i < reserve.length; i++) {
      if (isValid(lost, reserve[i])) {
        lost = lost.filter((item) => item !== isValid(lost, reserve[i]));
      }
    }
    const resultReserve = n - lost.length;
    return resultReserve;
  }

이 방식으로 문제를 풀어도 정답이 잘 나오지만 문제 출제자의 의도와는 완전히 다른 문제 풀이 방식이기 때문에 추천드리진 않습니다! 개인적으로 재귀 함수를 연습하기 위해서 풀어본 방식입니다.

그렇다면 그리디하게 문제를 푸는 방법은 어떤 방식일까요?

탐욕법 (Greedy)

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

 // 1. 현재 학생별 운동복 보유 수
 let student = new Array(n).fill(1);
 for (let i = 0; i < student.length; i++) {
   if (lost.includes(i + 1)) {
     student[i] -= 1;
   }
   if (reserve.includes(i + 1)) {
     student[i] += 1;
   }
 }

 // 2. 운동복이 2개 있는 학생들이 0인 친구들에게 빌려주기
 for (let i = 0; i < student.length; i++) {
   if (student[i] === 2 && student[i - 1] === 0) {
     student[i] -= 1;
     student[i - 1] += 1;
   }
   if (student[i] === 0 && student[i - 1] === 2) {
     student[i] += 1;
     student[i - 1] -= 1;
   }
 }

 for (let i = 0; i < student.length; i++) {
   if (student[i] === 0) {
     answer--;
   }
 }
 
 return answer;
}

그리디 알고리즘을 사용해서 문제를 푼 경우입니다. 전체 학생만큼 새로운 배열에 1을 담아서 만듭니다.
ex n = 5 , [1,1,1,1,1]

이 후에 체육복을 잃어버린 학생의 번호에 -1 해줍니다.

ex lost = [2,4], [1,0,1,0,1]

마지막으로 여분의 옷을 가지고 있는 학생의 번호에 +1 해줍니다.

ex reserve = [1,5], [2,0,1,0,2]

이런식으로 학생들이 가지고 있는 옷의 갯수를 하나의 배열에 담아서 양 옆에 있는 학생이 옷을 도둑질 당했다면 2에서 -1을 해주고 0에서 +1을 해주는 방식입니다.

ex 최종 결과 [1,1,1,1,1];

정리

문제 출제자의 의도에 맞게 잘 작성된 코드라고 생각이 듭니다! 앞으로도 출제자의 의도를 잘 생각하면서 문제를 풀어보겠습니다!