프로그래머스: 체육복(탐욕법/그리디)

알고리즘 초보답게 아~주 오래 걸려서 풀었다.
오래걸린건 덤이고 테스트케이스 실패할 때마다 내가 놓친 부분을 검색해가면서 풀었다.

해결과정

1. level1이지만 도저히 푸는 방법이 감이 안잡혀서 절망
   =>탐욕법이 뭔지 탐색시작

   
   👉탐욕법: 현재 상황에서 가장 최선의 선택을 하는 것(최적해를 찾는 알고리즘X)
   👉사용이유:
   (1) 항상 최적해를 구할 수 있을 때 수행시간이 동적계획법보다 훨씬 빠르기 때문에
   (2) 제약사항 때문에 최적해를 찾기 어려운 경우 근사해를 찾을 때 사용

2. 어떤식으로 풀어야 하는지 감 잡고 풀기시작
   =>테스트케이스 약 50점맞고 절망
   =>문제 다시 읽으면서 놓친 부분 발견

   

3. 놓친 부분 수정했지만 테스트케이스 7번만 자꾸 실패(절망)
   =>질문하기에서 단서 찾음: 앞번호-뒷번호 순서로 탐색 후 체육복 빌려주는 경우 정렬을 사용해보라는 글 발견 후 정렬로 해결
   =>통과

풀이정리

1. 여분을 갖고있는 학생이 도난 당한 경우
   👉filter를 사용해서 [lost]와 [reserve]의 중복되는 번호를 제거
2. filter로 걸러진 [reserve]의 순서를 오름차순으로 정렬
3. 'while'문을 사용해서 여분을 갖고있는 학생이 자신의 앞번호-뒷번호 순으로 탐색 후 빌려줌
   성공적으로 빌려준 경우 answer+1
4. 제출

코드

function solution(n, lost, reserve) {
    var i = 0;
  
  //여분을 갖고 있는 학생이 도난당했을 경우 빌려주지 못함
  //=>lost와 reserve리스트에서 겹치는 학생을 삭제
    var lost_filter = lost.filter(function(a){
        return reserve.indexOf(a) === -1;
    })
    var reserve_filter = reserve.filter(function(a){
        return lost.indexOf(a) === -1;
    })
    //여분이 있는 학생을 오름차순으로 정렬
    reserve_filter.sort((a,b)=>a-b)

  	//현재 answer(체육수업 들을 수 있는 학생 수): 전체학생(n)-잃어버린학생(lost_filter)
    var answer = n-lost_filter.length;
  
  //여분이 있는 학생이 자신의 앞번호 먼저 탐색하고 빌려줌 => 뒷번호 탐색하고 빌려줌
  //=>answer(체육수업 들을 수 있는 학생 수)+1
    while(i<reserve_filter.length){
        if(lost_filter.indexOf(reserve_filter[i]-1) !== -1){
            lost.splice(lost_filter.indexOf(reserve_filter[i]-1),1)
            answer += 1;
            console.log('-1','i:',i,'lost:',lost,'answer:',answer)
            i++;
        }else if(lost_filter.indexOf(reserve_filter[i]+1) !== -1){
            lost_filter.splice(lost_filter.indexOf(reserve_filter[i]+1),1)
            answer += 1;
            console.log('+1','i:',i,'lost:',lost,'answer:',answer)
            i++;
        }else{
            i++
        }
    }
    return answer;
}