Algorithm - lev1 체육복(탐욕법)

프로그래머스 level1 체육복

내 풀이(85/100)

function solution(n, lost, reserve) {
  let count = lost.length;

  lost.forEach(e => {
    const correct = reserve.indexOf(e);
    const front = reserve.indexOf(e - 1);
    const back = reserve.indexOf(e + 1);
    if (correct >= 0) {
      reserve.splice(correct, 1);
      count -= 1;
    } else if (front >= 0) {
      reserve.splice(front, 1);
      count -= 1;
      return;
    } else if (back >= 0) {
      reserve.splice(back, 1);
      count -= 1;
      return;
    }
  });
  return n - count;
}

• 탐욕법으로 소개되어 있는 문항이라고 하는데, 탐욕법이 뭔지 몰라서 일단 아는 선에서 한번 풀었다. 점수가 깎인 이유는 아마 특정 케이스에서 학생의 최댓값을 구하지 못해서인 것 같다.

탐욕법

• 선택의 순간마다 당장 눈앞에 보이는 최적의 상황만을 쫓아 최종적인 해답에 도달하는 방법

탐욕법 문제 해결과정

• 선택 절차(Selection Procedure): 현 상태에서의 최적의 해답 선택.
• 적절성 검사(Feasibility Check): 선택된 해가 문제의 조건을 만족하는지 검사.
• 해답 검사(Solution Check): 원래의 문제가 해결되었는지 검사, 해결되지 않았다면 선택 절차로 돌아가 위 과정 반복.

탐욕 알고리즘의 조건

• 탐욕적 선택 속성(Greedy Choice Property) : 앞의 선택이 이후의 선택에 영향을 주지 않는다.
• 최적 부분 구조(Optimal Substructure) : 문제에 대한 최종 해결 방법은 부분 문제에 대한 최적 문제 해결 방법으로 구성된다.

풀이

function solution(n, lost, reserve) {
  // students 초기화 - 학생들은 체육복 개수 1로 초기화
  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++) {
    // 체육복 0 | 1 을 가진 학생들을 대여 불가능이기 때문에 continue
    if (students[i] === 0 || students[i] === 1) continue;
    // 이전 번호의 학생이 있고 그 학생이 0개의 체육복을 가졌다면
    if (i !== 0 && students[i - 1] === 0) {
      // 이전 학생 증가
      students[i - 1]++;
      // 자신은 대여해줬으니 감소
      students[i]--;
    }
    // 인덱스 학생이 1개 초과한 체육을 가지고 다음 번호의 학생이 있고 그 학생이 0개의 체육복을 가졌다면
    if (students[i] > 1 && i + 1 !== len && students[i + 1] === 0) {
      // 다음 학생 증가
      students[i + 1]++;
      // 자신은 대여해줬으니 감소
      students[i]--;
    }
  }
  // 체육복 1개 이상을 가진 학생들의 수 반환
  return students.filter((v) => v >= 1).length;
}

• 나의 경우, 체육복을 잃어버린 사람을 기준으로 양옆번호만을 확인했다면, 풀이는 전체 학생을 배열로 생성해서 배열을 전부 순회하면서 최적의 선택을 하는 방식을 택했다. 탐욕법 설명을 읽어봐도 잘 이해가 되지 않지만 어떤 느낌인지는 와닿는 것 같다.