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

레벨 1의 문제는 기록해야겠다는 생각을 해보지않았는데 의외의 히든케이스가 많아 시간을 꽤나 잡아먹어서 기록해야겠다고 생각했다..

문제

입출력 예시

주의할 점

1. 여벌의 체육복을 가져온 학생이 체육복을 도난당한 경우도 있다. 이때 이 학생은 체육복이 하나 남은 걸로 가정하여 다른학생에게는 체육복을 빌려 줄 수 없다.

   n=5 , lost=[2,3], reserve=[1,2] 로 예를 들어보면 return값은 4가 나와야한다.
   WHY? 2번학생은 lost와 reserve에 모두 포함되어있기 때문에 체육복을 빌려줄 수 없다.

• 해결법으로 lost와 reserve 배열에 중복되어 있는 학생을 filter를 통해 제외시켰다.
  

2. 테스트케이스가 정렬되어 있지 않다면 ..?

   위 예시의 순서만 바꿔서
   n=5, lost=[3,2], reserve=[2,1] 로 예를 들면 return값은 똑같이 4 가 나와야하지만 정렬이 되어 있지 않다면 배열을 순회할때 3번학생이 2번학생의 체육복을 빌려가버린다. 얼마나 억울하겠는가 ! 이런 경우를 대비해 정렬해주자

최종코드

function solution(n, lost, reserve) {

    // 여벌의 체육복을 가지고 있는 도난당한 학생들을 다 제외
    let realLost=lost.filter((l)=>!reserve.includes(l));
    let realReserve=reserve.filter((r)=>!lost.includes(r));
    
    let num = realLost.length
    
    // 정렬을 안해주면 [4,2],[3,5] 같은 케이스를 해결해주지 못함
    realLost.sort()
    realReserve.sort()

    for(let i=0;i<realLost.length;i++){
        let item = realLost[i]
        
        for(let j=0;j<realReserve.length;j++){
            let item2 = realReserve[j]
            if(Math.abs(item-item2) == 1) {
                num --;
                realReserve.splice(j,1)
                break;
            }
        }

    }
    return n-num
}

테스트케이스에 대한 많은 정보가 없다하더라도 많은 반례들을 생각해보고 대입해보자 !
오랫동안 고민하다 테스트케이스를 무작위로 추가해가며 히든케이스를 찾았다.. 많은 경우의 수를 생각해보자