[프로그래머스] 체육복

그리디 알고리즘

어차피 모든 경우의 수를 다 고려할 필요가 없다. 눈에 보이는 대로 매칭하고 안되는 것은 버린다. 따라서 오름차순 또는 내림차순 소팅을 통해 하나씩 해보고 안되면 바로 버리면서 진행하면 풀린다.

접근

1. 빌려 줄 수 있는 사람들은 빌려줄 수 있지만 안되는 경우는 가차없이 버리기 위해 여분의 체육복이 있는 사람들을 정렬한다.
2. 빌려줄 수 있으면 카운트하고 빌려줄 수 없으면 버린다.
3. 체육복 못빌린 사람들만 남는다.

소스코드

function solution(n, lost, reserve) {
  var lost = lost.sort((a, b) => {
    return b-a;
  });
  var reserve = reserve.sort((a, b) => {
    return b-a;
  });
  
  // 체육복 여벌 있었는데 없어진 친구는 제외
  var reserve_fin = [];
  while (reserve.length) {
    if (lost.includes(reserve[0])) {
      let idx = lost.indexOf(reserve[0])
      reserve.shift()
      lost.splice(idx, 1)
    } else {
      reserve_fin.push(reserve[0])
      reserve.shift()
    }
  }
  reserve = reserve_fin
  
  // 여분이 있는 친구들 중에서 앞사람 빌려줄 수 있으면 바로 빌려준다. 
  // 앞사람 안되면 뒷사람 빌려준다. 
  // 이마저도 안되면 어차피 못빌려주니 과감히 버린다. 
  while (reserve.length) {
    try {
      if (lost.includes(reserve[0] - 1)) {
        let idx = lost.indexOf(reserve[0]-1)
        reserve.shift()
        lost.splice(idx,1)
        answer += 1
      } else if (lost.includes(reserve[0] + 1)) {
        let idx = lost.indexOf(reserve[0] + 1)
        reserve.shift()
        lost.splice(idx, 1)
        answer += 1
      } else {
        reserve.shift()
      }
    } catch (e) {
      break;
    }
  }
  
  // 전체에서 아직도 체육복 못빌린 사람 빼주면 정답이 된다.
  return n-lost.length;
}