점심시간에 도둑이 들어, 일부 학생이 체육복을 도난당했습니다. 다행히 여벌 체육복이 있는 학생이 이들에게 체육복을 빌려주려 합니다. 학생들의 번호는 체격 순으로 매겨져 있어, 바로 앞번호의 학생이나 바로 뒷번호의 학생에게만 체육복을 빌려줄 수 있습니다. 예를 들어, 4번 학생은 3번 학생이나 5번 학생에게만 체육복을 빌려줄 수 있습니다. 체육복이 없으면 수업을 들을 수 없기 때문에 체육복을 적절히 빌려 최대한 많은 학생이 체육수업을 들어야 합니다.
전체 학생의 수 n, 체육복을 도난당한 학생들의 번호가 담긴 배열 lost, 여벌의 체육복을 가져온 학생들의 번호가 담긴 배열 reserve가 매개변수로 주어질 때, 체육수업을 들을 수 있는 학생의 최댓값을 return 하도록 solution 함수를 작성해주세요.
제한사항
전체 학생의 수는 2명 이상 30명 이하입니다.
체육복을 도난당한 학생의 수는 1명 이상 n명 이하이고 중복되는 번호는 없습니다.
여벌의 체육복을 가져온 학생의 수는 1명 이상 n명 이하이고 중복되는 번호는 없습니다.
여벌 체육복이 있는 학생만 다른 학생에게 체육복을 빌려줄 수 있습니다.
여벌 체육복을 가져온 학생이 체육복을 도난당했을 수 있습니다. 이때 이 학생은 체육복을 하나만 도난당했다고 가정하며, 남은 체육복이 하나이기에 다른 학생에게는 체육복을 빌려줄 수 없습니다.
입출력 예
| n | lost | reserve | return |
|---|---|---|---|
| 5 | [2, 4] | [1, 3, 5] | 5 |
| 5 | [2, 4] | [3] | 4 |
| 3 | [3] | [1] | 2 |
입출력 예 설명
예제 #1
1번 학생이 2번 학생에게 체육복을 빌려주고, 3번 학생이나 5번 학생이 4번 학생에게 체육복을 빌려주면 학생 5명이 체육수업을 들을 수 있습니다.
예제 #2
3번 학생이 2번 학생이나 4번 학생에게 체육복을 빌려주면 학생 4명이 체육수업을 들을 수 있습니다.
나의 풀이
function solution(n, lost, reserve) {
let reserves = reserve.filter(v=> !lost.includes(v)).sort((a,b)=>a-b)
let losts = lost.filter(v=> !reserve.includes(v)).sort((a,b)=>a-b)
for(let i = 0; i< losts.length; i++){
for(let j = 0; j < reserves.length; j++){
if(losts[i] === reserves[j]-1){
losts.splice(i,1);
reserves.splice(j,1);
j--;
continue;
}
else if(losts[i] === reserves[j]+1){
losts.splice(i,1);
reserves.splice(j,1);
j--;
}
}
}
return n-losts.length
}이 문제는 꽤나 고비가 많았다. 문제는 여러 가지 있었는데, 문제는 크게
- for 반복문 자체의 오류
- 순서가 크기대로 정렬되지 않은 경우
- 여벌옷을 가지고 있었는데 원래 옷을 도난당하는 경우
가 있었다.
일단 첫 번째 반복문 자체의 문제.
for(let i = 0; i< losts.length; i++){
for(let j = 0; j < reserves.length; j++){
if(losts[i] === reserves[j]-1){
losts.splice(i,1);
reserves.splice(j,1);
continue;
}
else if(losts[i] === reserves[j]+1){
losts.splice(i,1);
reserves.splice(j,1);
}
} 원래는 이런 식으로 j--를 써주지 않았다. 체육복을 빌려준 다음 원래 배열에 해당하는 값을 지워주려고 splice를 써줬다. splice 자체는 원 배열을 바꿔주기 때문에, 만약 j--를 쓰지 않는다면, 배열의 다음 값을 검사하는 것이 아니라 건너뛰고 검사할 것이다. 예를 들어, losts[0]과 reserves[0]-1 값이 같다면, 각 배열의 0번째 인덱스를 삭제한다. 그리고 위의 조건 j++때문에 인덱스 1번값을 검사하는데 reserves의 현재 인덱스 1번은 원래 reserves의 2번 인덱스였기 때문에 결국 한 값을 건너뛰고 검사하게 되는 것이다. splice()로 원래 배열을 자르고 반복문을 사용할 때는 반드시 j--값을 넣어줄 것을 기억하자.
두 번째는 순서가 크기대로 정렬되지 않은 경우이다. 이 검사에서는 일단 여분옷을 갖고 있는 사람이 앞번호부터 차례차례 빌려주게 되는데, 값이 거꾸로 되어있다면 최대로 빌려줄 수가 없게 된다.
세 번째는 여벌옷을 갖고 있었지만 도난당해서 원래 옷을 자기 자신에게 빌려주어야 하는 경우이다. 처음에는
function solution(n, lost, reserve) {
let reserves = reserve.filter(v=> !lost.includes(v))이렇게만 써줬다. 여벌옷 부분만 확인해주면 된다고 생각해서 이렇게 사용했는데, 이렇게 되면 여벌 옷이 있을 때 자기 옷을 안 빌리고 남의 옷을 빌리게 된다. 그래서 lost값도 reserve와 값이 같은 부분을 배열에서 삭제해 줘야 한다.
참고할 풀이
function solution(n, lost, reserve) {
let reserves = reserve.filter(v=>!lost.includes(v)).sort((a,b)=>a-b);
let losts = lost.filter(v=>!reserve.includes(v)).sort((a,b)=>a-b);
return n - losts.filter(a => {
const b = reserves.find(r => Math.abs(r-a) === 1)
if(!b) return true
reserves = reserves.filter(r => r !== b)
}).length
}원래는 테스트케이스가 추가되어서 안 되는 풀이인데, 앞 부분에 자기 자신에게 빌려주는 경우를 써 주면 돌아가는 풀이이다. reserves에서 losts를 뺀 값의 절대값이 1인 경우를 찾아서 b에 할당해준 다음, b에 해당하지 않는 나머지를 걸러주는 풀이이다.
