점심시간에 도둑이 들어, 일부 학생이 체육복을 도난당했습니다. 다행히 여벌 체육복이 있는 학생이 이들에게 체육복을 빌려주려 합니다. 학생들의 번호는 체격 순으로 매겨져 있어, 바로 앞번호의 학생이나 바로 뒷번호의 학생에게만 체육복을 빌려줄 수 있습니다. 예를 들어, 4번 학생은 3번 학생이나 5번 학생에게만 체육복을 빌려줄 수 있습니다. 체육복이 없으면 수업을 들을 수 없기 때문에 체육복을 적절히 빌려 최대한 많은 학생이 체육수업을 들어야 합니다.
입출력 예시
n : 5
lost: [2, 4]
reserve: [1, 3, 5]
-> 5
function solution(n, lost, reserve) {
var answer = 0;
var numArr = new Array(n).fill(1);
var countArr = new Array(n).fill(0);
for (var i=0; i<lost.length; i++) {
numArr[lost[i] - 1]--;
}
for (var i=0; i<reserve.length; i++) {
numArr[reserve[i] - 1]++;
if (numArr[reserve[i] - 1] > 1) {
if (reserve[i] != 1) {
countArr[reserve[i] - 2]++;
}
if (reserve[i] != n) {
countArr[reserve[i]]++;
}
}
}
for (var i=0; i<n; i++) {
if (numArr[i] >= 1) {
continue;
} else if (countArr[i] == 1) {
numArr[i]++;
if (i < n - 2) {
countArr[i + 2]--;
}
} else if (countArr[i] == 2) {
numArr[i]++;
}
}
answer = numArr.filter(n => n >= 1).length
return answer;
}
탐욕법 다 까먹어서 한참을 걸려서 풀었다...
머리가 굳었나봄
어찌저찌 풀었다는 데에 의의가 있는 것 아닌감😄
했는데
생각해보니까 내 코드가 이상한 것 같다는 싸한 느낌이
테스트 케이스 하나 더 넣어서 확인해봤는데 틀렸더라.
n : 5
lost: [2, 4]
reserve: [1, 5]
-> 5
위 예시로 넣으면 틀리게 나온다.
그래서 수정...
...
function solution(n, lost, reserve) {
var answer = 0;
var numArr = new Array(n).fill(1);
lost.forEach(l => numArr[l - 1]--);
reserve.forEach(r => numArr[r - 1]++);
for (var i=0; i<n; i++) {
if (numArr[i] == 2 && numArr[i - 1] == 0) {
numArr[i]--;
numArr[i - 1]++;
}
if (numArr[i] == 2 && numArr[i + 1] == 0) {
numArr[i]--;
numArr[i + 1]++;
}
}
answer = numArr.filter(n => n >= 1).length;
return answer;
}
정다압