탐욕법(Greedy)

프로그래머스 탐욕법 문제입니다.

---

미래를 생각하지 않고 각 단계에서 가장 최선의 선택을 하는 기법
즉, 각 단계에서 최선의 선택을 한 것이 전체적으로 최선이길 바라는 알고리즘

작성 코드

---

function solution(n, lost, reserve) {
    
    /*
        Greedy 알고리즘
        미래를 생각하지 않고 각 단계에서 가장 최선의 선택을 하는 기법 
        
        n: 학생의 수, lost: 도난 학생 번호, reserve: 여벌 학생 번호
        
        
        먼저 lost === reserve 인 학생들은 lost, reserve에서 제거가 아니라 -1로 채운다.
        sort된 reserve에서 lost[i] - 1, lost[i] + 1 번호가 있는지 확인
        1. 있다면 lost, reserve에서 제거가 아니라 -1로 채운다. => 수업 참가 가능 
        2. 없다면 넘어간다.
        3. 수업에 참여할 총 학생수는 n - lost.length 
        
    */
  
  //reserve와 lost에 동일한 학생이 있다면 -1로 채우기
  //여벌 옷이 있는 학생과 도난 당한 학생이 동일하다면 빌려줄 순 없고 수업에 참가만 할 수 있는 학생이므로 lost, reserve에서 제거
    for (let i = 0; i <= lost.length - 1; i++) {
        for (let j = 0; j <= reserve.length - 1; j++) {
            if (lost[i] === reserve[j]) { 
                lost[i] = -1;
                reserve[j] = -1;
                break;
            }    
        }
        
    }
    
  	// -1 인 요소를 정리하기 
    let sortLost = lost.filter(el => el > -1);
    let sortReserve = reserve.filter(el => el > -1);
   
  //여벌 옷을 갖고 있는 학생이 도난 당한 학생에게 체육복을 빌려줄 수 있다면 lost에 있는 학생은 수업에 참가할 수 있고, 여벌 옷을 갖고 있는 학생은 더 이상 빌려줄 수 없으므로 둘 모두 제거
    for (let i = 0; i <= sortLost.length - 1; i++) {
        for (let j = 0; j <= sortReserve.length - 1; j++) {
            if (sortLost[i] === sortReserve[j] || (sortLost[i] + 1) === sortReserve[j] || (sortLost[i] - 1) === sortReserve[j]){
                sortLost[i] = -1;              
                sortReserve[j] = -1;
                
                break;
            }       
        }
    }
   
    let newLost = sortLost.filter(el => el > -1);
    var answer = n - newLost.length;
    return answer;
}

어려웠던 점

---

• 처음에 indexOf를 이용해 값이 존재하는지 찾으려고 했다. (이중 반복문을 쓰면 코드를 잘 못 짠 것같은 느낌..) 하지만 indexOf를 사용하면 해당 index를 찾기가 번거로워졌고 실제로

 //여벌 옷을 갖고 있는 학생이 도난 당한 학생에게 체육복을 빌려줄 수 있다면 lost에 있는 학생은 수업에 참가할 수 있고, 여벌 옷을 갖고 있는 학생은 더 이상 빌려줄 수 없으므로 둘 모두 제거
    for (let i = 0; i <= sortLost.length - 1; i++) {
        for (let j = 0; j <= sortReserve.length - 1; j++) {
            if (sortLost[i] === sortReserve[j] || (sortLost[i] + 1) === sortReserve[j] || (sortLost[i] - 1) === sortReserve[j]){
                sortLost[i] = -1;              
                sortReserve[j] = -1;
                
                break;
            }       
        }
    }

이 구문에서 indexOf를 사용해 풀면 (sortReserve.indexOf(sortLost[i])) sortLost[i] , sortLost[i] + 1, sortLost[i] - 1 중 어떤 값이 같은지 알 수 없으므로 sortReserve에 index를 찾기 어려워진다. 이러한 문제때문에 좀 어렵게 풀었는데 이 부분을 해결하니 쉽게 해결할 수 있었다.