42862. 체육복

코딩테스트 연습 - 체육복

문제 유형	난이도	걸린 시간	해결 유무(✅/❌)
탐욕법(그리디)	lv.1	1시간	✅

설계 방법

• Set을 사용해서 reserve 와 lost 의 차집합으로 reserveSet , lostSet 을만든다.

• reserveSet 을 순회하면서 앞의 학생이 체육복이 없다면 체육복을 빌려주고

• 뒤의 학생이 체육복이 없다면 체육복을 빌려준다.

• 총 학생에서 lostSet.size 만큼을 제거한다.

코드

Set.prototype.difference = function (setB) {    let difference = new Set(this);    for (let elem of setB) {        difference.delete(elem);    }    return difference;};
function solution(n, lost, reserve) {    const reserveSet = new Set(reserve).difference(new Set(lost));    const lostSet = new Set(lost).difference(new Set(reserve));
    reserveSet.forEach((i) => {        if (lostSet.has(i - 1)) {            lostSet.delete(i - 1);        } else if (lostSet.has(i + 1)) {            lostSet.delete(i + 1);        }    });
    return n - lostSet.size;}

시간 복잡도

☝ Set의 has , delete , add 연산이 O(1) 이라는 점을 새롭게 알게 되었다. (배열은 O(n))

• N = reserveSet , M = lostSet

• 차집합 생성 : O(N), O(M)

• reserveSet 순회 및 lostSet 검색 : O(NM)

• 총 O(NM)

어려웠던 점

• 그리디 알고리즘에 대한 이해가 부족했다.

참고자료

How to make your code faster using JavaScript Sets