점심시간에 도둑이 들어, 일부 학생이 체육복을 도난당했습니다. 다행히 여벌 체육복이 있는 학생이 이들에게 체육복을 빌려주려 합니다. 학생들의 번호는 체격 순으로 매겨져 있어, 바로 앞번호의 학생이나 바로 뒷번호의 학생에게만 체육복을 빌려줄 수 있습니다. 예를 들어, 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명이 체육수업을 들을 수 있습니다.
[풀이]
일단 정말 어려웠던 문제다. 레벨1에서 카카오 문제 제외하고 제일 어려운 문제라고 한다.
푸는데 어려워서 구글링하면서 참고해서 문제를 풀었다.
function solution(n, lost, reserve) {
const lostStudent = lost
.sort((a, b) => a - b)
.filter((el) => !reserve.includes(el));
let reserveStudent = reserve
.sort((a, b) => a - b)
.filter((el) => !lost.includes(el));
const noUniform = lostStudent.filter((lost) => {
const lendedStudent = reserveStudent.find(
(reserve) => Math.abs(lost - reserve) === 1
);
if (!lendedStudent) return lost;
reserveStudent = reserveStudent.filter((el) => el !== lendedStudent);
});
return n - noUniform.length;
}
1. 먼저 실제로 잃어버린 학생과 실제로 빌려줄 수 있는 학생을 구분해야한다.
제한사항에 여벌이 있는 학생도 도난을 당할 수 있다. 라고 쓰여져 있다.
이때 도난을 당한 여벌이 있는 학생은 다른 학생에게 빌려 줄 수 없다.
따라서, 여벌이 있는 학생이지만 실제로는 빌려줄 수 없으므로 실제로 잃어버린 학생과 여유분이 있는 학생 어느 곳에도 낄 수 없다.
2. 순서가 뒤바뀌어 나올 케이스를 대비해 오름차순으로 정렬해준다. (순서대로 있어야 생각하기 편하다.)
3. filter함수를 이용해 실제로 잃어버린 학생과 실제 빌려줄 수 있는 학생을 구분해야 한다.
// 실제로 잃어버린 학생
const lostStudent = lost
.sort((a, b) => a - b)
.filter((el) => !reserve.includes(el));
// 실제로 빌려줄 수 있는 학생
let reserveStudent = reserve
.sort((a, b) => a - b)
.filter((el) => !lost.includes(el));
오름차순 정렬을 하고 reserve(여벌 있는 학생) 배열에서 요소를 포함하고 있는지 체크해준다.
!reserve.includes(el)은 lost 와 reserve 를 비교했을 때 reserve 배열 안에 있는 요소와 같은 것을 제외하고 반환한다.
생각해봤을 때, 만약
lost = [2, 3, 4] 이고
reserve = [1, 3, 5] 일 때 [3]은 여벌이 있지만 도난 당한 학생이다.
결과적으로 실제로 잃어버린 학생은
lost.filter((el) => !reserve.includes(el))이므로 [2, 4]가 되고
실제로 여벌이 있는 학생은
reserve.filter((el) => !lost.includes(el))이므로 [1, 5]가 된다.
4. 체격이 안맞거나 여벌 옷이 없어 체육복이 없는 학생을 구해야 한다.
결국, (전체 학생 수 - 체육복이 없는 학생)이 답이 된다.
const noUniform = lostStudent.filter((lost) => {
const lendedStudent = reserveStudent.find(
(reserve) => Math.abs(lost - reserve) === 1
);
if (!lendedStudent) return lost;
reserveStudent = reserveStudent.filter((el) => el !== lendedStudent);
});
return n - noUniform.length;
}
체육복이 없는 학생은 실제 체육복이 없는 학생을 대상으로 filter함수를 적용해야한다.
그리고 체육복을 빌려준 학생은
여벌을 가지고 있는 학생(reserveStudent)에서 체격차이가 1만큼 나는 학생을 찾는다.
이때 find를 통해서 잃어버린 친구보다 체격이 더 작은 친구를 구해야 한다.
예시)
lost = [2, 4]이고 reserve = [1, 3]이면
1이 2를 빌려주고 3이 4를 빌려줘야 한다.
이때 3이 2를 빌려주면 1에게 빌려줄 사람이 없다. 따라서 lost 배열에서 앞 사람 부터 빌려주게 해야함.
그리고 빌려 줄 사람이 없으면(체격차이가 1이 나지 않으면) 그대로 lost를 리턴한다.
마지막으로 reserveStudent(여벌이 있는 학생)에서 빌려준 학생 수를 제외하고 받아준다.
예시)
n = 3 , lost = [2, 4] reserve = [3] 일때
lendedStudent = [3]이 되고 더이상 빌려줄 사람이 없기 때문에
if문에 들어가 lost = [4]를 반환하며, 결국 noUniform의 길이는 1이다.
따라서 3 - 1 = 2 이다.
풀때도 어려웠고 다시 정리할때도 헷갈리고 오래 걸렸던 문제다.
리팩토링이 필요할 것 같다!
'코딩 테스트 > Programmers - 1' 카테고리의 다른 글
[JS] 모의고사 (0) | 2022.10.06 |
---|---|
[JS] 폰켓몬 (0) | 2022.10.06 |
[JS] x만큼 간격이 있는 n개의 숫자 (0) | 2022.10.04 |
[JS] 하샤드 수 (1) | 2022.10.04 |
[JS] 정수 내림차순으로 배치하기 (0) | 2022.10.04 |