체육복 도난 사건

설명 : https://programmers.co.kr/learn/courses/30/lessons/42862

간단한 설명 : 반 학생들이 체육복을 한장씩 가지고 있거나 여벌을 가지고 있는 학생들이 있다. 근데 어떤 도둑놈이 와서 학생들 체육복을 훔쳐갔다. 그래서 하나도 없는 학생에게 여벌을 가지고 있는 학생이 빌려주기로 한것이다.
인자 n은 총 학생 명수 lost는 체육복을 잃어 버린 학생의 번호 배열, reserve는 여벌을 가지고 있는 학생의 번호 배열이다.

제한 사항

• 2 <= n <= 30
• 1 <= lost.length <= n
• 여벌 체육복은 도난 당하지 않는다.
• 여벌 체육복이 아닌 체육복을 도난 당할수 있다. 그렇게 되면 체육복이 하나기 때문에 빌려 줄수가 없다.
• 신체별로 번호를 배정을 했기 때문에 바로 앞뒤 번호에게만 체육복을 빌려 줄 수 있다.

전략:

일단 스토리대로 코드를 짜다가 탐욕 (greedy) 알고리즘으로 풀려고 했다.

function solution(n, lost, reserve) {
  let result = [];
  // 체육복 세팅
  for (let i = 0; i < n; i++) result.push(1);
  // 여벌 가지고 온 학생들 추가!
  for (let i = 0; i < reserve.length; i++) result[reserve[i] - 1]++;
  // 체육복 도난당한 애들 마이너스
  for (let i = 0; i < lost.length; i++) result[lost[i] - 1]--;
  for (let i = 0; i < result.length; i++) {
    if (result[i] === 2) { // 만약에 result 배열 중 2벌을 가지고 있는 사람이 있다면
      if (i >= 0 && result[i - 1] === 0) {
        result[i - 1]++;
        result[i]--;
      } else if (i >= 0 && result[i - 1] === 2) {
        result[i + 1]++;
        result[i]--;
      } else if (i <= n && result[i + 1] === 0 && result[i - 1] === 0) {
        result[i + 1]++;
        result[i]--;
      } else if (i <= n && result[i + 1] === 0) {
        result[i + 1]++;
        result[i]--;
      }
    }
  }
  return result.filter((ele) => ele > 0).length;
}

 이렇게 해놓고 풀었다고 좋아했는데 정리하다가 보니까 필요 없는 조건들이 2개나 있었다. 그래서 빼고

function solution(n, lost, reserve) {
  let result = [];
  // 체육복 세팅
  for (let i = 0; i < n; i++) result.push(1);
  // 체육복 도난당한 애들
  for (let i = 0; i < lost.length; i++) result[lost[i] - 1]--;
  for (let i = 0; i < reserve.length; i++) result[reserve[i] - 1]++;
  for (let i = 0; i < result.length; i++) {
    if (result[i] === 2) {
      //=> 만약에 여벌 갖고 있는 학생의 앞번호에게 빌려주는 걸로 가정한다.
      if (i >= 0 && result[i - 1] === 0) {
        result[i - 1]++;
        result[i]--; 
        //=> 앞전호는 위 조건에서 다 커버하기때문에 다음 조건에서는 앞에 번호를 커버시켜준다.
      } else if (i <= n && result[i + 1] === 0) {
        result[i + 1]++;
        result[i]--;
      }
    }
  }
  return result.filter((ele) => ele > 0).length;
}

 이것도 좋은 코드라고 할순 없지만 좀더 생각해서 리팩토링해야겠다.

회고 : 남들 처럼 멋지게 풀고 싶지만 ㅠ 실력이 모자란다.