← 12주차 · 체크포인트 2
보통그리디

체육복 나눠주기

학생 수 n, 체육복을 도난당한 학생 번호 배열 lost, 여벌 체육복이 있는 학생 번호 배열 reserve가 주어져요. 학생은 1번부터 n번까지 있어요.

체육복이 없는 학생은 바로 앞 번호나 바로 뒤 번호 학생에게만 여벌을 빌릴 수 있어요. 체육 수업을 들을 수 있는 학생 수의 최댓값을 반환해요.

주의할 점이 하나 있어요. 여벌이 있지만 자기 체육복을 도난당한 학생은, 그 여벌을 자기가 입어야 해서 남에게 빌려줄 수 없어요.

예시

예시 1
입력
n = 5, lost = [2, 4], reserve = [1, 3, 5]
출력
5
설명
1이 2에게, 3이나 5가 4에게 빌려주면 다섯 명 모두 들을 수 있어요.
예시 2
입력
n = 5, lost = [2, 4], reserve = [3]
출력
4
설명
3은 2나 4 중 한 명에게만 빌려줄 수 있어서 한 명은 못 들어요.
예시 3
입력
n = 3, lost = [3], reserve = [1]
출력
2
설명
1은 3에게서 멀어 빌려줄 수 없어서 3은 못 들어요.

제한 사항

  • 1 ≤ n ≤ 30
  • 1 ≤ lost.length, reserve.length ≤ n (없으면 빈 배열)
  • 같은 학생이 lost와 reserve 양쪽에 있을 수 있어요.
학생마다 체육복 개수를 세요(기본 1, 도난이면 -1, 여벌이면 +1). 개수가 2인 학생만 빌려줄 수 있어요. 번호 순서대로 보면서 개수가 2인 학생은 앞 번호에 먼저, 없으면 뒤 번호에 빌려줘요. 마지막에 체육복이 1개 이상인 학생을 세요.
javascript
function gymUniform(n, lost, reserve) {
  const has = new Array(n + 2).fill(1);
  for (const l of lost) has[l] -= 1;
  for (const r of reserve) has[r] += 1;
  for (let i = 1; i <= n; i++) {
    if (has[i] !== 2) continue;
    if (has[i - 1] === 0) {
      has[i - 1] = 1;
      has[i] = 1;
    } else if (has[i + 1] === 0) {
      has[i + 1] = 1;
      has[i] = 1;
    }
  }
  let count = 0;
  for (let i = 1; i <= n; i++) if (has[i] >= 1) count++;
  return count;
}
이전 문제합이 target인 최단 구간
다음 문제예산 배정
에디터를 불러오고 있어요…
코드를 작성하고를 눌러 예시 테스트를 확인해 보세요.