프로그래머스 체육복 (greedy) - 자바스크립트 풀이

프로그래머스

탐욕법을 이용하여 문제를 풀었다. 

각 단계에서 최적의 선택을 하는 탐욕법을 이용해보자. 

각 배열을 정렬한 후 인접한 학생끼리 우선적으로 처리한다. 여벌 체육복을 가진 학생이 앞 또는 뒷자리 학생에게 빌려줄 수 있는 경우, 빌려주고 그에 따라 빌린 학생은 체육복을 도난당한 학생들 배열에서 삭제한다.  그로 인해 이미 빌려준 학생은 다시 확인할 필요가 없어져 최선의 선택이 가능해진다. 

여벌 체육복을 가져온 학생이 체육복을 도난당했을 수 있습니다. 이때 이 학생은 체육복을 하나만 도난당했다고 가정하며, 남은 체육복이 하나이기에 다른 학생에게는 체육복을 빌려줄 수 없습니다.

위 조건에 따라 여벌을 가져온 학생과 체육복을 도난당한 학생이 일치하는 경우에 대해 filter를 수행해준다.

    let filteredLost = lost.filter(x => !reserve.includes(x));
    let filteredReserve = reserve.filter(x => !lost.includes(x));

 

이 후 오름차순으로 정렬을 해준다.

    filteredLost.sort((a,b) => a - b);
    filteredReserve.sort((a,b) => a - b);

우선 처음에 answer 변수 값은 (전체 학생 수 - 체육복을 잃어버린 학생 수) 로 정의하자.

  let answer = n - filteredLost.length;

    for(let i = 0; i < filteredReserve.length; i++){
    // 체육복을 가져온 학생 배열을 for문으로 돌아보자
        let lendIndex = filteredLost.findIndex(x => Math.abs(x - filteredReserve[i]) === 1);
	// 체육복을 도난당한 학생의 번호와 현재 인덱스 값에 해당하는 체육복을 가진 학생 번호의 차의 절대값이 1인 경우
    //-> 체육복을 빌려줄 수 있다!
        if(lendIndex !== -1){
            answer++;
            filteredLost.splice(lendIndex, 1); // 체육복을 빌려주었으므로 배열에서 해당 학생은 삭제한다
        }
    }

최종 코드

function solution(n, lost, reserve) {
    let i = reserve.length;

    let filteredLost = lost.filter(x => !reserve.includes(x));
    let filteredReserve = reserve.filter(x => !lost.includes(x));

    filteredLost.sort((a,b) => a - b);
    filteredReserve.sort((a,b) => a - b);

    let answer = n - filteredLost.length;

    for(let i = 0; i < filteredReserve.length; i++){
        let lendIndex = filteredLost.findIndex(x => Math.abs(x - filteredReserve[i]) === 1);

        if(lendIndex !== -1){
            answer++;
            filteredLost.splice(lendIndex, 1);
        }
    }


    return answer;
}