[JS] 프로그래머스 - 체육복

---

---

문제

점심시간에 도둑이 들어, 일부 학생이 체육복을 도난당했습니다. 다행히 여벌 체육복이 있는 학생이 이들에게 체육복을 빌려주려 합니다. 학생들의 번호는 체격 순으로 매겨져 있어, 바로 앞번호의 학생이나 바로 뒷번호의 학생에게만 체육복을 빌려줄 수 있습니다. 예를 들어, 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. reserve와 lost에 겹쳐진 숫자가 있을 수 있다. 이 경우를 대비해 겹쳐진 수 들을 제외 해 주어야 한다. 즉, 자기 자신이 2개의 체육복 중 하나를 잃어버린 것. 이 것은 아무도 빌려줄 수 없다.
2. lost와 reserve가 정렬이 됐다는 보장은 없다.
3. 양 옆을 다 살피긴 해야 하겠지만 이전 친구에게 체육복을 빌릴 수 있다면 이전 친구에게 빌려야 더 많은 사람들을 빌려줄 수 있다. 이전에 없다면 이후를 확인한다.

그리고 이걸 풀게 되면 이중 for 문이 나오게 될 텐데, 그 것은 시간복잡도가 상당해지므로(풀리긴 함) 우리는 딕셔너리를 사용 할 것 이다.

function solution(n, lost, reserve){ // onlyLost와 onlyReserve는 서로 겹치는 사람이 없이 순수 배열을 만들어주기 위함이다. let onlyLost = [...lost].filter(x => !reserve.includes(x)); let onlyReserve = [...reserve].filter(x => !lost.includes(x)); // 이 둘이 정렬이 돼 있다는 확신이 없으므로 정렬도 시켜주자. onlyLost = onlyLost.sort((x, y) => x - y); onlyReserve = onlyReserve.sort((x, y) => x - y); // 우선 답은 전체 학생 수 에서 체육복이 없는 학생 수 일 것이다. let answer = n - onlyLost.length; // 이중 for문을 만들지 않기 위한 딕셔너리를 만들어주자. let isHaveCloth = {}; // 그리고 확실하게 체육복을 가지고 있는 학생들의 key를 true로 만들어주자.active for(let i = 0 ; i < onlyReserve.length; i++){ isHaveCloth[onlyReserve[i]] = true; } // 이제 체육복이 없는 학생들의 key를 돌면서 양 옆에 체육복을 빌려줄 수 있는 학생이 있나 살펴보자. for(let i = 0 ; i < onlyLost.length; i++){ // 우선 이 전에 빌려줄 수 있는 학생이 있을까? if(isHaveCloth[onlyLost[i] - 1]){ answer += 1; isHaveCloth[onlyLost[i] - 1] = false; // 이 후에 있다면 }else if(isHaveCloth[onlyLost[i] + 1]){ answer += 1; isHaveCloth[onlyLost[i] + 1] = false; } } return answer }