프로그래머스 체육복 Greedy 탐욕법 문제 Javascript

 

프로그래머스 체육복 문제

 

프로그래머스 체육복 문제는 탐욕법으로 풀어보는 것이다. 탐욕법 알고리즘은 각 단계에서 최적이라고 고려되는 것을 선택하는 것을 반복하는 방법이다. 현재 선택이 마지막까지 적용되는 경우 탐욕법으로 문제를 풀어볼 수 있다. 

 

 

체육복 문제에서는 앞에있는 학생이 체육복을 빌려줄수도 있고, 뒤에 있는 학생이 빌려줄수도 있다. 따라서 가장 우선해서 옷을 빌려줄 순서를 정해야 한다. 

먼저 옷을 잃어버린 학생과 빌려줄수 있는 학생 배열을 생성하고, 학생순서대로 스캔해나가면서 옷을 빌려줄 관계를 설정해주면 된다. 

프로그래머스 체육복 자바스크립트

 

배열이 생성된 후로 옷을 잃어버린 학생들의 배열을 순회하면서 옷을 빌려줄 수 있는 경우(Math.abs(r-l) === 1) count를 증가하면서 최종적으로 체육시간에 참여할 수 있는 학생의 수를 카운팅 한다. 

 

 

function solution(n, lost, reserve) {
  // 체육복을 도난당한 학생들 중 여벌 체육복을 가진 학생들 제거
  const filteredLost = lost.filter((l) => !reserve.includes(l));
  const filteredReserve = reserve.filter((r) => !lost.includes(r));
  // 체육복을 빌려줄 수 있는 학생 수 계산
  let count = n - filteredLost.length;

  filteredLost.forEach((l) => {
    const index = filteredReserve.findIndex((r) => Math.abs(r - l) === 1);
    if (index !== -1) {
      filteredReserve.splice(index, 1);
      count++;
    }
  });

  return count;
}

 

탐욕 알고리즘으로 매 분기별로 가장 최적의 해를 찾아내는 알고리즘이다. 

 

 

 

1. lost와 reserve에서 중복되는 학생의 수를 제거한다. 여벌을 가지고 있는 학생이 체육복을 도난당한 경우도 존재하기 때문.

2. 체육복을 빌려줄 수 있는 학생은 전체 학생에서 옷을 잃어버린 학생의 수를 뺀 나머지로 초기화한다.

3. filteredLost에 담긴 학생들을 순회하면서 앞뒤로 체육복을 빌려줄 수 있는 사람의 index를 찾고, filteredReserved 배열에서 제거한 뒤 count를 증가시킨다.

4. 최종적으로 count에 담긴 학생의 수가 체육복을 빌려줄 수 있는 학생의 수가 된다.  

 

 

🚀️ 도움이 되셨다면 구독과 좋아요 부탁드립니다 👍️

 

프로그래머스 완주하지 못한 선수 해시 맵 사용 풀이 파이썬

 

Github CLI Install Ubuntu 22.04