Younho9 NotesProgrammers 42862. 체육복
Title
Programmers 42862. 체육복
Category
AlgorithmTags
Aliases
Programmers 42862. 체육복Created
3 years ago
Updated
last year
| 문제 유형 | 난이도 | 걸린 시간 | 해결 유무(✅/❌) |
|---|---|---|---|
| 탐욕법(그리디) | lv.1 | 1시간 | ✅ |
설계 방법
Set을 사용해서
reserve와lost의 차집합으로reserveSet,lostSet을만든다.reserveSet을 순회하면서 앞의 학생이 체육복이 없다면 체육복을 빌려주고뒤의 학생이 체육복이 없다면 체육복을 빌려준다.
총 학생에서
lostSet.size만큼을 제거한다.
코드
javascript
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.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)
어려웠던 점
- 그리디 알고리즘에 대한 이해가 부족했다.