[JS] 탐욕법(Greedy) > 체육복

여벌이 있는 학생(=옷이 2벌 이상인 학생)만 옷이 없는 학생에게 옷을 빌려줄 수 있다는 것에 MAP이나 배열을 사용하면 되겠다고 생각했다.

map으로 한다하면 key에는 학생번호, value에는 옷 개수, 배열로 한다면 인덱스+1이 학생번호, 값이 옷 개수

map으로 풀어봤다.

function solution(n, lost, reserve) {

    var answer = 0;
    
    var list = new Map();
    
    //전체 학생들에게 체육복 1씩 증정
    for(var i = 1; i <= n; i++){
        list.set(i, 1);
    }
    //Map { 1 => 1, 2 => 1, 3 => 1, 4 => 1, 5 => 1 }

    //여벌이 있는 학생들 +1
    for(var i = 0; i < reserve.length; i++){
        list.set(reserve[i], list.get(reserve[i])+1);
    }
    //Map { 1 => 2, 2 => 1, 3 => 2, 4 => 1, 5 => 2 }
    
    //도난당한 학생들 -1
    for(var i = 0; i < lost.length; i++){
        list.set(lost[i], list.get(lost[i])-1);
    }
    //Map { 1 => 2, 2 => 0, 3 => 2, 4 => 0, 5 => 2 }
    
    for(var i = 1; i <= list.size; i++){
        
        if(list.get(i) == 2 && list.get(i+1) == 0){
            list.set(i, 1);
            list.set(i+1, 1);
        }else if(list.get(i) == 0 && list.get(i+1) == 2){
            list.set(i, 1);
            list.set(i+1, 1);
        }
        
        if(list.get(i) >= 1){
            answer++;
        }
    }
    return answer;
}

꽤 빠른 속도로 통과했다~~~~ :)

var list = new Map();
    
    //전체 학생들에게 체육복 1씩 증정
    for(var i = 1; i <= n; i++){
        list.set(i, 1);
    }
    //Map { 1 => 1, 2 => 1, 3 => 1, 4 => 1, 5 => 1 }

    //여벌이 있는 학생들 +1
    for(var i = 0; i < reserve.length; i++){
        list.set(reserve[i], list.get(reserve[i])+1);
    }
    //Map { 1 => 2, 2 => 1, 3 => 2, 4 => 1, 5 => 2 }
    
    //도난당한 학생들 -1
    for(var i = 0; i < lost.length; i++){
        list.set(lost[i], list.get(lost[i])-1);
    }
    //Map { 1 => 2, 2 => 0, 3 => 2, 4 => 0, 5 => 2 }

map에 전체 학생들 수를 세팅해주고 값은 1(옷 한 벌)씩 넣어줬다.

여벌이 있는 학생들은 옷 개수를 1씩 더해주었고, 옷을 도난당한 학생들은 옷을 1씩 빼주었다.

최종적으로 1번학생, 3번학생, 5번학생은 옷이 2벌씩 있고, 2번 학생 4번 학생은 옷이 없어서 앞/뒤 번호 학생에게 옷을 빌려야 한다.

for(var i = 1; i <= list.size; i++){
        
        if(list.get(i) == 2 && list.get(i+1) == 0){
            list.set(i, 1);
            list.set(i+1, 1);
        }else if(list.get(i) == 0 && list.get(i+1) == 2){
            list.set(i, 1);
            list.set(i+1, 1);
        }
        
        if(list.get(i) >= 1){
            answer++;
        }
    }

map의 크기만큼 반복했다.

만약 앞 번호 학생이 2벌의 옷을 갖고 있고, 뒤 번호 학생이 옷이 0벌이라면, 옷을 한 벌 빌려줘야하니 

앞 번호 학생의 옷을 1벌로 세팅해주고, 뒤 번호 학생 옷도 1벌로 세팅해준다.

만약 앞 번호가 0벌이고 뒤 번호가 2벌인 경우에도 옷을 빌려줄 수 있으니 각각 한 번씩 가지게 되는 것으로 세팅해준다.

옷 세팅이 끝나면 기준 번호(i) 학생의 옷이 1벌 이상인 경우에는 answer를 1씩 더해준다.