[프로그래머스] 체육복 | JavaScript

탐욕 알고리즘(greedy algorithm)

탐욕 알고리즘은 최적해를 구하는 데에 사용되는 근사적인 방법으로, 여러 경우 중 하나를 결정해야 할 때마다 그 순간에 최적이라고 생각되는 것을 선택해 나가는 방식으로 진행하여 최종적인 해답에 도달한다. - 위키백과

• 탐욕 알고리즘의 정의를 보고 네비게이션이 생각이 났다. 아빠가 운전하는 차를 타고 가면서 카카오맵 네비를 쓴 적이 있는데 몇분 간격으로 실시간 교통정보와 경로를 불러오더라. 그걸 토대로 최적의 길과 다른 길로 가게 되면 얼마가 더 걸리는지도 알려준다.

체육복을 빌려줘 🏃🏻‍♂️

• 체육시간이 다가오는데, 일부 학생들이 체육복을 도난을 당한 경우다. 다행히 여벌의 체육복을 가져온 학생들이 빌려주기로 한다. 학생들의 번호는 체격 순으로 매겨져 있으며 바로 앞번호나 바로 뒷번호의 학생에게만 빌려줄 수 있다. 체육복이 없으면 체육시간에 참여할 수 없기때문에 최대한 많은 학생들이 들을 수 있도록 하자!
• 전체 학생의 수 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

코드

function solution(n, lost, reserve) {
  // 여벌 체육복을 가져온 학생이 도난을 당한 경우, lost와 reserve 둘 다 해당되지 않는다고 볼 수 있다.
  // 따라서 실제 도난당한 학생들과 여벌 체육복 학생들을 구한다.
  let realLost = lost.filter((el) => !reserve.includes(el));
  let realReserve = reserve.filter((el) => !lost.includes(el));

  return (
    n -
    realLost.filter((lostEl) => {
      // 여벌 체육복을 가져온 학생 중 도난 당한 학생과의 체격차가 1인 학생
      let abs = realReserve.find((reserveEl) => Math.abs(lostEl - reserveEl) == 1);
      // 체격차가 1이 아닐 경우 그대로 realLost에 반환
      if (!abs) return true;
      // 체격차가 1인 학생은 한사람에게 빌려줄 수 있으므로 다음 realReserve에서 제외
      realReserve = realReserve.filter((reserveEl) => reserveEl !== abs);
    }).length
  );
}

배열 메서드들 칭찬해~

알고리즘 문제를 풀다보면 `map()`, `filter()`, `find()` 등의 메서드들을 자주 사용하는데 사용방법만 알고 있고 잘 사용하면 가독성이 좋아지고 코드의 양을 줄일 수 있다!

이 알고리즘을 보고...

정말 멘붕이었다. 어떻게 풀지 막막해서 구글링을 하면서 참고를 많이 했다. 이곳저곳을 보면서 나를 위한 것만은 아닌 기록 블로그를 보고 코드 작성을 시작했다. 🧑🏻‍💻 이해도 잘 되고 참신한 문제 해석에 감탄했다.