[프로그래머스] 체육복

개발잘하기프로젝트·2020년 11월 7일
0
post-thumbnail

🤔 문제

탐욕법(Greedy)

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

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

❗️ 제한

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

💡 접근

체육복 여벌이 있는 학생들 중 도난당한 학생, 도난당한 학생들 중 여벌이 없는 학생, 여벌이 있는 학생들 중 본인의 체육복을 해결하고 진짜로 빌려줄 수 있는 학생을 찾아낸다.

생각하는 것을 글로 표현하는게 항상 어렵다...

중요한 것은 본인이 잃어버렸을 경우 본인의 여벌로 해결하고 수업에 참여해야하기 때문에, 체육복을 잃어버린 학생과 체육복을 빌려줄 수 있는 학생이 중복되는 경우를 체크해야한다.

🧑🏻‍💻 코드

function solution(n, lost, reserve) {
  // 여벌이 있는 학생들 중에서 도난당한 학생들 추출
  const rich = reserve.filter((_, i, arr) => lost.includes(arr[i]));
  
  // 도난당한 학생들 중 여벌이 없는 학생들 추출
  const poor = lost.filter((_, i, arr) => !rich.includes(arr[i]));
  
  // 여벌이 있는 학생들 중에서 본인의 체육복을 해결하고 진짜로 빌려줄 수 있는 학생들 추출
  const rest = reserve.filter((_, i, arr) => !rich.includes(arr[i]));
  
  // rest 학생들 중에서 poor 학생들에게 빌려줄 수 있는 학생
  const rent = rest.filter(
    (r, i, arr) => poor.includes(arr[i] + 1) || poor.includes(arr[i] - 1),
  );
  
  // 정말로 수업에 참여하지 못하는 학생
  // rent해줄수 있는 인원수에 맞게 poor에서 제외
  if (!rent.length) return n - poor.length;
  if (rent.length && poor.length <= rent.length) return n;
  if (rent.length && poor.length > rent.length)
    return n - poor.length + rent.length;
}

📝 참고

MDN - Array.prototype.includes()
includes() 메서드는 배열이 특정 요소를 포함하고 있는지 판별합니다

profile
🏠 ☕️ 🎞 🌿 + 🧑🏻‍💻

0개의 댓글