1. 체육복 빌려주기

총 학생수, 체육복을 잃어버린 아이들과 여벌의 체육복이 있는 아이들이 담긴 배열이 각각 입력된다. 아이들의 번호가 높으면 치수가 크고 낮으면 치수가 작다. 그래서 바로 이전의 번호를 가진 학생, 또는 바로 다음 번호를 가진 학생에게만 체육복을 빌려줄 수 있다.

그리고 여분의 체육복을 가진 아이들중에 체육복을 잃어버린 아이들이 있을 수 있다. 이때, 체육복을 최대한 많이 빌려주자. 그랬을 때, 체육시간에 참석할 수 있는 총 학생수를 리턴하자.

예를 들어, 다음과 같이 정보가 주어졌다고 해보자.

n   lost         reserve
5   [2, 4]       [1, 3, 5]
5   [1, 2, 4, 5] [4, 5]

첫번째 경우: 이때, 1번이 2번에게 3번이 4번에게 빌려주면 모두가 체육복을 입을 수 있게 된다. 그래서 5명이 리턴된다.
두번째 경우: 이때는 4,5번 모두 체육복이 하나밖에 없으므로 빌려줄 수 가 없다. 따라서 1,2번은 체육수업에 참석을 못한다. 따라서 3명이 리턴된다.

2. 접근 방법

두 가지 해법을 적어보려고 한다.

1. 첫번째 해법

• pseudo code
  • 총학생수에서 lost학생수를 빼서 초기값을 설정
  • 여벌이 있는데 체육복을 도난 당한 학생수를 찾음
    • 있으면 초기값에서 1을 더함
  • 여벌도 없고 체육복을 도난 당한 학생수를 찾음
    • reserve에서 빌려줄 수 있으면 초기값에 1을 더함

const solution1 = (n, lost, reserve) => {
  let answer = n - lost.length;

  // 여벌이 있는데 체육복을 도난 당한 학생수를 찾음
  lost = lost.filter((lostStudent) => {
    let revIdx = reserve.findIndex(
      (reserveStudent) => reserveStudent === lostStudent
    );
    // 여벌이 있는 사람중에 도난당한 사람이 없으면 그냥 그대로 lost배열을 둔다
    if (revIdx === -1) return lostStudent;
    // 그런사람이 있으면 reserve에서 제외한다.
    // 그리고 그런 사람이 있으면 일단은 체육복을 입을 수 있다는 거니깐 원래 answer에서 1을 추가
    else {
      reserve.splice(revIdx, 1);
      answer++;
    }
  });

  // 여벌도 없고 체육복을 도난 당한 학생수를 찾음
  lost.forEach((lostStudent) => {
    let revIdx = reserve.findIndex(
      (reserveStudent) => Math.abs(lostStudent - reserveStudent) === 1
    );

    if (revIdx !== -1) {
      reserve.splice(revIdx, 1);
      answer++;
    }
  });

  return answer;
};

2. 두 번째 해법

• pseudo code
  • filter, find를 통해서 최종적으로 체육복을 못빌린 사람 수를 n 에서 빼면 된다.
    • lost에서 filter를 이용해서 reserve에 있는 학생 중 빌릴 수 있는 경우를 알아본다.(빌릴 수 있는 학생을 b라고 한다.)
      • 있으면, reserve 에서 b를 filtering한다.
      • 없으면, true를 리턴해서 lost에 그대로 남게 한다.

function solution2(n, lost, reserve) {
  let answer = 0;
  let unable = 0;

  unable = lost.filter((a) => {
    const b = reserve.find((r) => Math.abs(r - a) <= 1);

    // 현재 lost학생(a)이 여벌을 가진 학생중 빌릴 사람 있는지 확인, Math.abs(r-a) <= 1 앞,뒤 번호인지 확인
    // 그리고 0이라고 하면 여벌을 가진 학생중에 도난 당한 학생이므로 자기 자신것 밖어 없으니깐
    // 이 학생도 체육복을 일단 입을 수 있기 있다. 그래서 b에 담는것이다.

    // abs는 두 숫자의 차이를 +형태로 바꾸어서 리턴 함.
    // abs를 사용하기 때문에 위의 코드보다 훨씬 간결해진 것 같음.

    if (!b) return true;

    reserve = reserve.filter((r) => r !== b); // 빌려준 사람을 제외한 나머지 사람만 필터링.
  }).length; // 빌려줄 수 없는 사람수 확인.

  return (answer = n - unable);
}

확실히 깔끔하기는 두번째 해답이 깔끔하다. abs를 이용해서 한번에 해결했다.
그러나 첫번째는 모든 테스트 케이스를 통과하지만 두번째는 마지막 테스트케이스에서만 실패가 뜬다. 이유가 무엇인지는 아직 잘 모르겠지만 로직이 좋아서 올려본다.

그렇다면 탐욕법에대해서 알아보자. 그리고 이 문제가 왜 탐욕법인지도 알아보자!

3. 탐욕법이란?

• 지금 선택이 나중의 선택과 전혀 무관한것 , 영향을 끼치지 않는 것이고

• 매순간의 최적해가 쌓여서 전체의 최적해가 되게 하는 것.대표적인게 다익스트라의 최단거리 알고리즘이다. 그럼 이 알고리즘에서 어떠한 개념이 탐욕법의 1,2와 연결되는지 설명해보겠다.

• 지금 선택이 나중의 선택과 전혀 무관한것 a->e로 가는 최단 경로를 구한다고 할 때 a -> c -> d -> f -> e 의 경로가 최단 경로라고 하자. 이때 a -> c의 경로를 선택한다고 해서 그게 무조건 d랑 연결될 필요는 없다.

c에서 다른 경로인 f랑도 연결될 수 있다. c 와 d는 서로 무관하게 존재하는 것일 뿐. 나는 서로 무관하게 존재하는 것을 선택할 뿐이다.

• 매순간의 최적해가 쌓여서 전체의 최적해가 되게 하는 것. a -> e 로 가는 최적해를 찾는 과정에서 모여진 경로는 각각 모두 최적해를 의미한다. 왜냐면 이 경로들중에 하나라도 최적해가 있지 않다면 전체경로가 최적해가 될 수 없기 때문이다. 7개의 색깔을 섞어서 100% 순도의 초록색 물감을 만드려면 7개의 색깔중에 하나라도 초록색과 다른 색깔이 들어가면 100% 초록색깔이 될 수 없는 것 처럼 말이다(비유가 적절할란지 모르겠다)

그래서 a -> e로 가는 경로가 모두 최적해다. 바꿔 말하면 a -> e로 가는 최단거리 사이에 존재하는 각각의 지점에 대한 최단거리도 함께 발견된다는 소리다. 그래서 a - > d로가는 최단거리 c -> f로 가는 최단거리도 발견되었다는 소리다.

그럼 체육복에서는 어떻게 적용할 수 있을까?

• 지금 선택이 나중의 선택과 전혀 무관한것 체육복이 있는 사람이 체육복이 없는 사람에게 빌려주는것이 여기에 해당되지 않을까? 예를 들어, // n= 5, lost = [2, 4, 5], reserve = [1, 2, 3] 라고 하자. 1번 학생이 여분의 체육복이 있고 2번학생에게 빌려줘도 되고 2번학생이 자신의 체육복을 그냥 입을 수도 있다. 1번학생이 체육복을 안빌려줬다고 해서 2번학생이 체육복을 빌려줄 수 있는 학생의 수가 줄어드는 것은 아니다.

여전히 1번학생과 무관하게 2번학생은 빌려줄 수 있는 사람 아무에게나 빌려줄 수 있다.

• 매순간의 최적해가 쌓여서 전체의 최적해가 되게 하는 것. 위와 같은 예시가 주어졌을때 1번이 2번에게 / 3번이 4번에게 빌려주고 남는 학생은 5번이 남게 된다.

이 보다 더 최적해가 있을까? 매순간의 최적해가 전체의 최적해가 되었다. 그리고 그 이외의 경우는 없다. 이로써 체육복 문제는 1,2번의 조건을 모두 만족시키므로 탐욕법이 맞다.

이렇게 해서 탐욕법에 대한 개념을 어느정도 잡았다. 탐욕법에 근거하여 이 문제를 어떻게 접근해야 했을까? reserve를 loop하든 lost를 loop하든 하나를 loop하면서 빌려줄 수 있는 사람을 찾고 빌려줬으면 지우면 된다.

그럼 차근차근 진행해나가면서 최적의 조건이 완성되는 것이다. 이런식으로 생각해보았는데 맞는지는 잘 모르겠다. 이제 탐욕법이라는 개념을 접했기 때문에 어떻게 적용할지 잘 모르는것이 너무나 당연하다.

아하!! 이름그대로 최소한의 노력으로 매순간 최적의 해를 찾고 그리고 전체의 최적의 해, 최대의 효율이 낼 수 있으면 되는 구나!이름의 의미를 잘 생각해보자!!

4. 배운 점

• findIndex: true로 리턴되는 idx가 할당이 되게 하는 api.

• abs: 양수를 뽑아내기 때문에 범위를 알아내는데 적합한 메소드인것 같다.