[Javascript] 프로그래머스- 탐욕법(Greedy)/ 체육복

https://programmers.co.kr/learn/courses/30/lessons/42862#

코딩테스트 연습 - 체육복

 

문제 설명

점심시간에 도둑이 들어, 일부 학생이 체육복을 도난당했습니다. 다행히 여벌 체육복이 있는 학생이 이들에게 체육복을 빌려주려 합니다. 학생들의 번호는 체격 순으로 매겨져 있어, 바로 앞번호의 학생이나 바로 뒷번호의 학생에게만 체육복을 빌려줄 수 있습니다. 예를 들어, 4번 학생은 3번 학생이나 5번 학생에게만 체육복을 빌려줄 수 있습니다. 체육복이 없으면 수업을 들을 수 없기 때문에 체육복을 적절히 빌려 최대한 많은 학생이 체육수업을 들어야 합니다.

전체 학생의 수 n, 체육복을 도난당한 학생들의 번호가 담긴 배열 lost, 여벌의 체육복을 가져온 학생들의 번호가 담긴 배열 reserve가 매개변수로 주어질 때, 체육수업을 들을 수 있는 학생의 최댓값을 return 하도록 solution 함수를 작성해주세요.

 

제한사항

• 전체 학생의 수는 2명 이상 30명 이하입니다.
• 체육복을 도난당한 학생의 수는 1명 이상 n명 이하이고 중복되는 번호는 없습니다.
• 여벌의 체육복을 가져온 학생의 수는 1명 이상 n명 이하이고 중복되는 번호는 없습니다.
• 여벌 체육복이 있는 학생만 다른 학생에게 체육복을 빌려줄 수 있습니다.
• 여벌 체육복을 가져온 학생이 체육복을 도난당했을 수 있습니다. 이때 이 학생은 체육복을 하나만 도난당했다고 가정하며, 남은 체육복이 하나이기에 다른 학생에게는 체육복을 빌려줄 수 없습니다.

입출력 예

n	lost	reserve	return
5	[2, 4]	[1, 3, 5]	5
5	[2, 4]	[3]	4
3	[3]	[1]	2

입출력 예 설명

예제 #1
1번 학생이 2번 학생에게 체육복을 빌려주고, 3번 학생이나 5번 학생이 4번 학생에게 체육복을 빌려주면 학생 5명이 체육수업을 들을 수 있습니다.

예제 #2
3번 학생이 2번 학생이나 4번 학생에게 체육복을 빌려주면 학생 4명이 체육수업을 들을 수 있습니다.

출처

 

 

풀이 1

function solution(n, lost, reserve) {
    
    let answer = 0;
    
    // 체육복을 도난당하고 여벌이 없는 학생(여벌 받아야하는 학생)
    const noReserveLost = lost.sort((a,b)=>a-b).filter((lost) => !reserve.includes(lost));
    
    // 여벌이 있고 체육복을 도난당하지 않은 학생(빌려줄 수 있는 학생)
    let hasReserve = reserve.sort((a,b)=>a-b).filter((reverse) => !lost.includes(reverse));
    
    const finalLost = noReserveLost.filter((lost) => {
        
        // 첫번째로 체육복을 빌려줄 수 있는 사람 
        const lend = hasReserve.find((reserve) => Math.abs(reserve - lost) == 1);
        
        // 체육복 빌려줄 사람이 없으면 그대로 lost 리턴
        if(!lend) return lost;
        
        // 빌려준 사람 제외하기
        hasReserve = hasReserve.filter((reverse) => reverse !== lend);
    })
  
    // 답 = 전체 학생 수 - 체육복이 없는 학생 수 
    answer = n - finalLost.length;
    
    return answer;
}

 

여기서 중요한 점은 체육복을 도난당했는데 여벌을 가지고 온 학생은 다른 학생한테 체육복을 빌려줄 수 없다는 것이다.

 

(전체 학생 수 - 체육복을 도난당하고 여벌을 못받은 학생 수 ) 가 답이다.

 

체육복을 도난당하고 여벌을 못받은 학생 수를 구해보자.

 

체육복을 도난당했으면서 여벌이 없는 학생 배열을 돌면서

체육복을 안도난당했고 여벌이 있는 사람들 중에 번호 차이가 1인 학생 번호를 찾는다. 

 

* find 함수는 판별 함수를 만족하는 첫번째 요소의 값을 반환한다. 

 

빌려줄 수 있는 학생이 없으면 lost를 그대로 리턴한다.

한 학생에게 여벌을 주고 나면 더이상 줄 수 없으므로 reserve 배열에서 제거한다. 

 

그렇게 도난당한 학생 중 본인에게 빌려줄 사람이 없는 학생만 필터링해 전체 학생 수에서 빼면

체육수업을 들을 수 있는 사람을 구할 수 있다. 

 

그런데 .... 90퍼만 통과하고 테스트케이스 전부를 통과하지 못했다.

테스트케이스가 몇개 더 추가가 되었던데 추가된 테스트케이스를 통과하지 못했나보다.

구글링해보니 lost 와 reserve 배열이 오름차순으로 주어지지 않을 케이스가 있기 때문에, sort 함수로 오름차순 시켜줘야 했다. 그렇게 하니 통과할 수 있었다. 

 

 

 

 

 

풀이 2

function solution(n, lost, reserve) {
    
    // 학생들이 가지고 있는 체육복 수를 모두 1로 세팅
    const clothes = Array(n).fill(1);
    
    // 체육복을 도난당한 학생들의 체육복 수를 0으로
    lost.map((lost) => {clothes[lost-1] = 0});
    
    // 여벌을 가지고 있는 학생들의 체육복 수 1 증가
    reserve.map(reserve => {clothes[reserve-1] += 1});

    for(let i=0; i<n; i++){
        // 체육복이 0개인 학생이 앞사람한테 받아왔을 때 
        if(clothes[i] === 0 && clothes[i-1] ===2){
            clothes[i] = 1;
            clothes[i-1] = 1;
        }
        // 체육복이 0개인 학생이 뒷사람한테 받아왔을 때 
        else if(clothes[i] === 0 && clothes[i+1] === 2){
            clothes[i] = 1;
            clothes[i+1]=1;
        }
    }
    
    // 체육복이 한개 이상인 학생들의 수
    return clothes.filter(c => c > 0).length;
}

 

 

조금 더 쉽게 접근한 방법.

 

배열을 만들어 학생들이 가지고 있는 체육복 개수를 1로 세팅한다. 

도난 당한 학생들을 먼저 0으로 만들고, 그 후 여벌이 있는 경우 1을 더해준다. 

이 때 여벌을 가져온 학생이 도난을 당했다면 위 방법을 통해 체육복 1개를 가지고 있게 된다.

체육복이 2개인 학생이 0개인 학생한테 체육복을 빌려 줄 수 있으므로

체육복이 0개인 학생의 바로 앞, 바로 뒤 학생이 체육복 2개를 가지고 있을 경우 빌려와 각각 1개가 된다. 

그렇게 조정된 배열에서 1개 이상의 체육복을 가지고 있는 학생의 수를 구하면 된다.