탐욕법(Greedy) > 체육복

https://school.programmers.co.kr/learn/courses/30/lessons/42862

프로그래머스

 

체육복 여분 가져온 사람의 배열을 하나씩 제거하면서 

없어질 때까지 while을 돌리고

빌려주기가 가능할 때 lost에서 하나씩 제거해가면서

마지막에 체육복 갯수에서 lost의 배열 갯수를 빼면 나올 줄 알았다

function solution(n, lost, reserve) {
    while (reserve.length > 0) {
        const reserveNum = reserve.pop();
        if (lost.includes(reserveNum - 1)) {
            lost.splice(lost.indexOf(reserveNum - 1), 1);
        } else if (lost.includes(reserveNum + 1)) {
            lost.splice(lost.indexOf(reserveNum + 1), 1);
        }
    }
    return n - lost.length;
}

 

73.3%만 정답이 되고 나머지는 안되는데

반례 중에는 중복된 체육복에 대한 처리가 있을 듯 하다

결국 정렬을 써서 해결 해야함

 

function solution(n, lost, reserve) {
    const actualLost = lost.filter(x => !reserve.includes(x));
    const actualReserve = reserve.filter(x => !lost.includes(x));

    actualLost.sort((a, b) => a - b);
    actualReserve.sort((a, b) => a - b);

    let borrowed = 0;
    for (const reserveNum of actualReserve) {
        const frontNum = reserveNum - 1;
        const backNum = reserveNum + 1;

        if (actualLost.includes(frontNum)) {
            actualLost.splice(actualLost.indexOf(frontNum), 1);
            borrowed++;
        } else if (actualLost.includes(backNum)) {
            actualLost.splice(actualLost.indexOf(backNum), 1);
            borrowed++;
        }
    }

    return n - actualLost.length;
}