프로그래머스 코테 - 체육복

https://school.programmers.co.kr/learn/courses/30/lessons/42862#

문제 설명

점심시간에 도둑이 들어, 일부 학생이 체육복을 도난당했습니다. 다행히 여벌 체육복이 있는 학생이 이들에게 체육복을 빌려주려 합니다. 학생들의 번호는 체격 순으로 매겨져 있어, 바로 앞번호의 학생이나 바로 뒷번호의 학생에게만 체육복을 빌려줄 수 있습니다. 예를 들어, 4번 학생은 3번 학생이나 5번 학생에게만 체육복을 빌려줄 수 있습니다. 체육복이 없으면 수업을 들을 수 없기 때문에 체육복을 적절히 빌려 최대한 많은 학생이 체육수업을 들어야 합니다.

전체 학생의 수 n, 체육복을 도난당한 학생들의 번호가 담긴 배열 lost, 여벌의 체육복을 가져온 학생들의 번호가 담긴 배열 reserve가 매개변수로 주어질 때, 체육수업을 들을 수 있는 학생의 최댓값을 return 하도록 solution 함수를 작성해주세요.

전체 학생의 수 n
체육복을 도난당한 학생들의 번호가 담긴 배열 lost
여벌의 체육복을 가져온 학생들의 번호가 담긴 배열 reserve
가 매개변수로 주어질 때, 체육수업을 들을 수 있는 학생의 최댓값을 return

제한사항

• 전체 학생의 수는 2명 이상 30명 이하입니다.
• 체육복을 도난당한 학생의 수는 1명 이상 n명 이하이고 중복되는 번호는 없습니다.
• 여벌의 체육복을 가져온 학생의 수는 1명 이상 n명 이하이고 중복되는 번호는 없습니다.
• 여벌 체육복이 있는 학생만 다른 학생에게 체육복을 빌려줄 수 있습니다.
• 여벌 체육복을 가져온 학생이 체육복을 도난당했을 수 있습니다. 이때 이 학생은 체육복을 하나만 도난당했다고 가정하며, 남은 체육복이 하나이기에 다른 학생에게는 체육복을 빌려줄 수 없습니다.

---

풀이

과정

입출력 예 1)
n = 5 전체 학생의 수
lost = [2, 4] 도난당한 학생 번호
reserve = [1, 3, 5] 여벌 체육복

• 체육복은 바로 앞 번호의 학생이나 뒷번호의 학생에게만 빌려줄 수 있음

그럼 2번은 1, 3에게 빌릴 수 있고 4번 학생은 3, 5에게 빌릴 수 있으니

• 2번이 1번한테 빌리면 4번은 3번, 5번한테 빌릴 수 있고
• 2번이 3번한테 빌리면 4번은 5번한테 빌릴 수 있고.. 5명 다 수업을 들을 수 있음

내가 생각한 방법
1. answer을 학생수(n)-체육복을도난당한학생들수(lost.length) 로 초기화
2. reserve에 lost[i]±1에 해당하는 값이 있으면 reserve를 filter로 lost[i]±1이 아닌 값의 배열로 바꿔놓고 answer에 1을 더해준다

function solution(n, lost, reserve) {
    let answer = n - lost.length;
    
    for(let i = 0; i < lost.length; i++) {
        if(reserve.includes(lost[i] - 1)) {
            reserve = reserve.filter(r => r !== lost[i] - 1);
            answer += 1;
        } else if(reserve.includes(lost[i] + 1)) {
            reserve = reserve.filter(r => r !== lost[i] + 1);
            answer += 1;
        }
    }
    
    return answer;
}

으아니..!

검색해 보다 나랑 비슷한 코드로 구현한 어떤 블로그에서 "여벌옷이 있지만(reserve) 도난(lost) 당한 사람은 여벌옷이 없는 것과 마찬가지가 된다. 따라서, 이 경우를 먼저 처리해 줘야 모든 테스트 케이스에 통과할 수 있다."를 봤다.
제한사항을 다시 읽어보니 여벌 체육복을 가져온 학생이 체육복을 도난당했을 수 있다. 이때 이 학생은 체육복을 하나만 도난당했다고 가정하며, 남은 체육복이 하나이기에 다른 학생에게는 체육복을 빌려줄 수 없다.라고 쓰여있어서 다시 도전

function solution(n, lost, reserve) {
    let answer = n - lost.length;
    let tmpLost = [];
    
    for(let i = 0; i < lost.length; i++) {
      if(reserve.includes(lost[i])) {
          reserve = reserve.filter(r => r !== lost[i]);
          answer++;
      } else {
          tmpLost.push(lost[i]);
      }
    }
    
    lost = tmpLost;
    
    for(let i = 0; i < lost.length; i++) {
        if(reserve.length < 0) return;
        if(reserve.includes(lost[i] - 1)) {
            reserve = reserve.filter(r => r !== lost[i] - 1);
            answer++;
        } else if (reserve.includes(lost[i] + 1)) {
            reserve = reserve.filter(r => r !== lost[i] + 1);
            answer++;
        }
    }
    
    return answer;
}

이것도 실패.. 이유는 잘 모르겠다😭

---

최종 풀이

다른 분의 풀이를 참고했는데 나처럼 테스트 한두개가 안 되는 것도 있었다;.;

function solution(n, lost, reserve) {
  let students = Array.from({ length: n }).fill(1);

  lost.forEach((target) => {
    students[target - 1]--;
  });

  reserve.forEach((target) => {
    students[target - 1]++;
  });

  for (let i = 0, len = students.length; i < len; i++) {
    if (students[i] === 0 || students[i] === 1) continue;
    if (i !== 0 && students[i - 1] === 0) {
      students[i - 1]++;
      students[i]--;
    }
    if (students[i] > 1 && i + 1 !== len && students[i + 1] === 0) {
      students[i + 1]++;
      students[i]--;
    }
  }
  return students.filter((v) => v >= 1).length;
}

다른 사람의 풀이

와오...

function solution(n, lost, reserve) {      
    return n - lost.filter(a => {
        const b = reserve.find(r => Math.abs(r-a) <= 1)
        if(!b) return true
        reserve = reserve.filter(r => r !== b)
    }).length
}

마무리

탐욕법이 뭔지랑 내 풀이가 왜 실패했는지 찾기