🕊 Link

Lv1. 체육복 Javascript
https://programmers.co.kr/learn/courses/30/lessons/42862

🧑🏻‍💻 Code(javascript)

function solution(n, l, r) {
  const arr = Array(n).fill(1);
  r.forEach((idx) => arr[idx - 1]++);
  l.forEach((idx) => arr[idx - 1]--);

  for (let i = 0; i < arr.length; i++) {
    if (arr[i] === 0 && arr[i + 1] === 2) {
      arr[i]++;
      arr[i + 1]--;
    } else if (arr[i - 1] === 2 && arr[i] === 0) {
      arr[i - 1]--;
      arr[i]++;
    }
  }

  let cnt = 0;
  arr.forEach((item) => {
    if (item === 0) cnt++;
  });
  return n - cnt;
}

💡 Solution

• greedy(그리디 | 탐욕법)

function solution(n, l, r) {
  // 학생수 만큼의 index를 가진 배열을 만들고 모두 count 1을 세팅
  const arr = Array(n).fill(1);
  // reverse(여분의 체육복이 있는 학생)들의 count를 +1
  r.forEach((idx) => arr[idx - 1]++);
  // lost(체육복을 도난당한 학생)들의 count를 -1
  l.forEach((idx) => arr[idx - 1]--);

  // 학생 배열을 돌면서 
  // 타겟이 0이고 타겟+1이 2인 경우를 찾아 분배
  // 타겟이 0이고 타겟-1이 2인 경우를 찾아 분배
  for (let i = 0; i < arr.length; i++) {
    if (arr[i] === 0 && arr[i + 1] === 2) {
      arr[i]++;
      arr[i + 1]--;
    } else if (arr[i - 1] === 2 && arr[i] === 0) {
      arr[i - 1]--;
      arr[i]++;
    }
  }

  // 최종적으로 체육복이 없는 학생을 count
  let cnt = 0;
  arr.forEach((item) => {
    if (item === 0) cnt++;
  });
  return n - cnt;
}

👨🏻‍💻💭 Self Feedback

그리디 알고리즘 : 전체가 아닌 각 단계에서의 최선을 탐색
불가능한 경우를 먼저 떠올리는 것도 좋지만, 때때로 독이 될 수도 있다.

• 2021.04.16 - 최초 작성

댓글 환영 질문 환영
by.protect-me