[JavaScript] 프로그래머스 코딩테스트 레벨 1 : 체육복

📌  문제

점심시간에 도둑이 들어, 일부 학생이 체육복을 도난당했습니다. 다행히 여벌 체육복이 있는 학생이 이들에게 체육복을 빌려주려 합니다. 학생들의 번호는 체격 순으로 매겨져 있어, 바로 앞번호의 학생이나 바로 뒷번호의 학생에게만 체육복을 빌려줄 수 있습니다. 예를 들어, 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

---

📌  풀이

알아야 하는 것

• 언젠간 풀린다는 낙관적인 생각? 하지만 언제나 그렇듯 컴퓨터는 잘못이 없다. 잘못은 내 코드가 한다.
• 여벌 체육복을 가지고 있는 학생이 체육복을 잃어버린 학생이 될 수 있다는 점

구할 것

• 여벌 체육복도 없이 진짜 체육복을 잃어버린 학생들과 잃어버리지 않고 진짜 여벌 체육복을 갖고 있는 학생 배열

이게 무슨 말이냐면, reserve 배열에 있는 학생이 lost 배열에도 있을 수 있다는 말이다. reserve 배열에 있는 학생이 체육복을 잃어버렸을 경우에는 자기가 입을 것 밖에 없기 때문에 다른 학생에게 빌려줄 수 없다. 따라서 reserve 배열과 lost 배열에서 겹치는 요소를 각각 제거해주어야 한다.

 

1. 교집합 되는 요소 제거

  let realLost = lost.filter((v) => !reserve.includes(v)).sort((a, b) => a - b);
  let canLend = reserve.filter((v) => !lost.includes(v)).sort((a, b) => a - b);

sort를 해주지 않으면 테스트 케이스에서 2개 실패하는데 이 반례는 조금 있다가 설명하겠다! (ㅠㅠ)

일단 이렇게 진짜 체육복을 잃어버리고, 진짜 체육복을 빌려줄 수 있는 아이들만 있도록 배열을 정리했다.

 

2. 빌려 입을 수 있는 아이 찾기

for (let i = 0; i < canLend.length; i++) {
    let lender = canLend[i];

    if (realLost.includes(lender - 1)) {
      realLost.splice(realLost.indexOf(lender - 1), 1);
    } else if (realLost.includes(lender + 1)) {
      realLost.splice(realLost.indexOf(lender + 1), 1);
    }
  }

체육복을 빌려줄 수 있는 canLend 배열을 순회하는 요소를 lender라고 하자.

체육복을 빌려줄 수 있는 조건은 lender와 차이가 1 나는 realLost의 요소이다.

따라서 조건문을 2개로 세워서 +1 차이가 나는 경우, -1 차이가 나는 경우를 둔다.

 

만약 realLost에 lender보다 1 큰 요소를 가지고 있다면, 그 요소의 인덱스를 찾고 splice로 그 요소를 아예 제거해준다.

왜냐하면 얘는 이미 lender에게 체육복을 빌려서 더 이상 realLost가 아니기 때문이다.

1 작은 요소를 갖고 있을 때 또한 동일하게 제거해준다.

 

3. 체육 활동을 할 수 있는 학생 구하기

 

체육복이 없으면 체육 활동을 할 수 없다.

체육복을 빌린 아이들은 realLost에서 하나씩 제거가 되었으므로, canLend 배열을 다 돌았을 때도 맞는 체육복을 찾지 못해 빌리지 못한 아이들은 realLost에 남게 된다. 즉 전체 학생 수 - realLost.length를 하면 답을 구할 수 있다.

 

function solution(n, lost, reserve) {
  let realLost = lost.filter((v) => !reserve.includes(v)).sort((a, b) => a - b);
  let canLend = reserve
    .filter((v) => !lost.includes(v))
    .sort((a, b) => a - b);

  for (let i = 0; i < canLend.length; i++) {
    let lender = canLend[i];

    if (realLost.includes(lender - 1)) {
      realLost.splice(realLost.indexOf(lender - 1), 1);
    } else if (realLost.includes(lender + 1)) {
      realLost.splice(realLost.indexOf(lender + 1), 1);
    }
  }

  return n - realLost.length;
}

---

번외

첫 번째 실패는 realLost, canLend처럼 교집합이 되는 요소를 빼지 않고 일단 다 합친 후에 제거한 게 패착이었다.

예를 들어 [1, 3, 4] [2, 4] 라고 했을 때 [2, 1] [2, 3] [2, 4] [4, 1] [4, 3], [4, 4] 이렇게 반복문을 중첩해서 만든 후 i와 j가 같은 경우만 제거했다.  수 많은 테스트 케이스 중에 반례를 만나 이 풀이는 드랍됐다. 그리고 일단 더 근본적인 문제가 있었다...

 

두 번째 실패는 realLost, canLend를 만들어놓고도 중첩을 한 게 패착이었다.

예를 들어 5, [2, 4, 5], [1, 3, 5]를 했을 때 [ [ 1, 2 ], [ 1, 4 ], [ 3, 2 ], [ 3, 4 ] ] 이렇게 조합이 구성되는데, 여기서 1씩 차이가 나는 경우를 모두 구했다. 그러면 3이 2한테도 빌려주고 4한테도 빌려주는 중복이 생기는 것이었다. 물론 뒤에 Set으로 [1, 3, 3]의 중복을 없애주었지만 근본적으로 이 부분에서 중복이 발생했기 때문에 계속해서 오류가 발생했던 것이었다.

  for (let i = 0; i < canBorrow.length; i++) {
    for (let j = 0; j < realLost.length; j++) {
      combination.push([canBorrow[i], realLost[j]]);
    }
  }

  for (let i = 0; i < combination.length; i++) {
    if (
      combination[i][1] - combination[i][0] === 1 ||
      combination[i][0] - combination[i][1] === 1
    ) {
      answer.push(combination[i][0]);
    }
  }

 

세 번째 실패는 지금 코드와 거의 똑같은데 realLost, canLend에 sort를 하지 않아서였다.

도대체 이게 뭔 상관이냐고 울부짖고 싶었는데 반례를 찾아서 할말 없을 무 됐음

6, [6, 2, 4], [1, 5, 3] 처럼 정렬이 되지 않을 경우 아래와 같이 진행된다.

 

1이 2에게 빌려줌 > [6, 4] [5, 3]

조건문에서 -1인 값이 먼저 걸려서 5가 4에게 빌려줌 > [6] [3]

이러면 총 2명만 빌려서 5명의 학생만 체육 활동을 할 수 있다.

 

정렬을 해주면 어떻게 될까?

[2, 4, 6] [1, 3, 5] 라면 1이 2에게 빌려주고, 3이 4에게 빌려주고, 5가 6에게 빌려줘 순차적으로 해결이 되는 것이다. 

애초에 문제에서 '최대 학생 수'를 구하는 것이어서 이 부분을 간과하면 안됐다.

 

반례 찾는 게 너무 힘들었다... 웬만한 반례 다 구했으니 여기서 찾아보시길 ㅎㅎ

//console.log(solution(5, [2, 4, 5], [1, 3, 5])); // 4
//console.log(solution(4, [3, 1], [2, 4])); // 4
//console.log(solution(5, [4, 2], [1, 3, 5, 6])); // 5
//console.log(solution(6, [6, 2, 4], [1, 5, 3])); // 6
//console.log(solution(5, [2, 4], [3])); // 4
//console.log(solution(3, [3], [1])); // 2
//console.log(solution(5, [3, 4], [1, 2, 5])); // 5
//console.log(solution(5, [4, 2], [3, 5])); // 5
//console.log(solution(5, [4, 5], [3, 4])); // 4
//console.log(solution(7, [2, 4], [1, 3])); // 7
//console.log(solution(13, [13, 6, 1], [11, 9, 8, 7])); // 11
//console.log(solution(5, [5], [4])); // 5
//console.log(solution(5, [1, 2], [3, 4])); // 4
//console.log(solution(13, [1, 2, 5, 6, 10, 12, 13], [2, 3, 4, 5, 7, 8, 9, 10, 11, 12])); // 11