[javascript] Programmers 탐욕법(Greedy) level1 체육복 <최신 테스트케이스>

문제

[Programmers] 탐욕법 level1 체육복

• 최신 테스트케이스 추가된 후 채점
  

풀이 #1 - 필터링하여 이용

👉정렬👈된 배열에서 필요한 데이터 필터링하여 사용
바로 앞번호 또는 뒷번호 계산 - Math.abs()로 한 번에 계산

const solution = (n, lost, reserve) => {
    lost.sort((x, y) => x - y);
    reserve.sort((x, y) => x - y);

    // 체육복을 빌려야 하는 학생 (여벌이 없고, 잃어버린 학생)
    const netLost = lost.filter((l) => !reserve.includes(l));
    // 체육복 빌려줄 수 있는 학생 (여벌 있고, 잃어버리지 않은 학생)
    let netReserve = reserve.filter((r) => !lost.includes(r));

    const absent = netLost.filter((lostStudent) => {
        // 앞뒤번호 학생 중 여벌 있는 학생의 번호
        const extra = netReserve.find((reserveStudent) => Math.abs(reserveStudent - lostStudent) <= 1);
        if (!extra) {
            return true;
        }
        // 여벌을 빌려준 뒤 netReserve 배열에서 해당 학생의 번호 제거
        netReserve = netReserve.filter((reserveStudent) => reserveStudent !== extra);
    });

    return n - absent.length;
}

풀이 #2 - 체육복 개수 배열 이용

👉정렬👈된 배열 이용

function solution(n, lost, reserve) {
    lost.sort((x, y) => x - y);
    reserve.sort((x, y) => x - y);
    
    const count = new Array(n); // 각 번호의 학생이 가진 체육복 개수 배열
    /* 1. 모든 학생이 체육복 1개씩 가진다고 가정 */
    count.fill(1);
    /* 2. 여벌 있는 학생의 경우 증가 */
    reserve.forEach((r) => {
        const index = r-1;
        if (!lost.includes(r)) {
            count[index] = 2; // 2개로 대체
        }
    });
    /* 3. 도난당한 학생 중 빌릴 수 있는지 체크 */
    lost.forEach((l) => {
    	if (!reserve.includes(l)) {
          const index = l-1;
          if (count[index-1] === 2) {
              count[index-1] = 1;
              count[index] = 1;
          } else if (count[index+1] === 2) {
              count[index+1] = 1;
              count[index] = 1;
          } else {
              // 빌리지 못한 경우
              count[index] = 0;
          }
	}
    });
    /* 4. 체육복 개수 1 이상인 경우 카운트 */
    const target = count.filter((c) => c >= 1);
    
    return target.length;
}

풀면서 전혀 가닥을 잡지 못한다고 생각한것에 비해
구글링해보니 접근법이 나쁘지 않았지만 막상 채점하면 실패하여 디버깅까지 했는데도
원인을 도무지 알 수 없었다
최적해 이론에 대한 이해도의 문제인가 했으나.. 👉정렬👈 문제였다