[프로그래머스] 체육복 (그리디) / javascript

아주 오랜만에 알고리즘을 풀어보려고 레벨 1부터 풀어봤는데,,
레벨 1이었지만 테스트케이스 12,13,14번 때문에 시간을 잡아먹어서 기록해본다..🥲

주의할 점

테케 12

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

예를 들어
n=5 lost=[2,3] reserve=[1,2] 이면 바른 return 값은 4인데
도난당하였으면서 여분 체육복을 가져온 2번학생은 다른 학생에게는 체육복을 빌려줄 수 없다고 문제에 적혀있다!

근데 나의 경우 제대로 읽지않고 풀어서 1번학생이 2번에게 빌려주고, 2번학생이 3번학생에게 빌려준다고 생각하면 5명 모두 체육수업에 참여할 수 있다고 생각하게되어서 오답이 나왔었다.

let realLost=lost.filter((l)=>!reserve.includes(l));
let realReserve=reserve.filter((r)=>!lost.includes(r));

lost, reserve 배열에서 같은 학생이 포함되어있으면 그 학생을 lost, reserve 배열에서 제외하고 시작한다.

테케 13,14

lost 배열이 정렬이 안되어있을 경우를 생각

12번은 문제 다시 읽어서 쉽게 해결했지만 이 테스트케이스에서 시간을 많이 썼다..ㅠ
정렬안되어있을 경우는 생각치못했었는데 질문목록 뒤져서 찾아냈다..ㅠㅠ

생각해보면 lost 배열이 정렬되어있지 않을때에는 제대로 동작하지 않을 수 있다.

n=5 lost=[4,2] reserve=[3,5] 이면 바른 return 값은 5인데
정렬하지 않으면 순서대로 배열을 순회하게되어서 4번학생은 3번에게 빌려주게 되고,
2번학생은 결국 여분 체육복을 받지 못해서 체육수업에 참여할 수 없기 때문에 총 가능한 학생수가 4명이 된다.

나의 경우 Lost 배열을 순회하면서 lost에 있는 학생번호보다 작은값부터 처리해주고 있어서 lost배열을 오름차순 정렬시켜주었다.
(큰값부터 처리해주고 있었다면 내림차순 정렬)

realLost.sort((a,b)=>a-b);

결론

테스트케이스

1) n=5 lost=[2,3] reserve=[1,2] return 4

2) n=5 lost=[4,2] reserve=[3,5] return 5

를 생각해보자!!

문제를 제대로 읽고!! 정렬 안되었을경우의 테케를 생각해보자!!

히든 테케 찾는게 젤 까다로운 것 같다 🥺

최종코드

function solution(n, lost, reserve) {
    var answer = n-lost.length;
    // 처음 가능한 학생수 = n - lost.length
    // lost 배열 앞뒤의 값을 reserve에 포함되어있는지를 확인 -> 해당값을 reserve에서 뺌 + answer++
    // 왜 정렬을 해줘야 하지? - [4,2], [3,5]와 같은 케이스 때문
    
    let realLost=lost.filter((l)=>!reserve.includes(l));
    let realReserve=reserve.filter((r)=>!lost.includes(r));
    answer+=lost.length-realLost.length;
    
    realLost.sort((a,b)=>a-b);
    
    realLost.forEach((l)=>{
        if(realReserve.length===0){
            return;
        }
        
        if(realReserve.includes(l-1)){
            realReserve=realReserve.filter((r)=>r!==l-1);
            answer++;
        }
        else if(realReserve.includes(l+1)){
            realReserve=realReserve.filter((r)=>r!==l+1);
            answer++;
        }
        
    })
    return answer;
}