알고리즘 - 체육복 도난사건,,,!!!!!

function solution(n, lost, reserve) {
    var answer = 0;
  let have = [];
  console.log(n); // 1~n까지의 학생
  for(let i = 1; i<=n; ++i) {
    if(!lost.includes(i)) 
      have.push(i);
  }

  console.log('체육복 갖고있는 학생: ' ,have); // 체육복 갖고 있는 학생
  // lost의 +-0~1이 reserve에 있는지?
  let help = [];
//   for(let i = 0; i < reserve.length; ++i) {
// 	help = lost.filter((el)=> reserve.includes(el) || reserve.includes(el-1)||
//                     reserve.includes(el+1))  
// }
  
   for(let i = 0; i < lost.length; ++i) {
	help = reserve.filter((el)=> lost.includes(el) || lost.includes(el-1)||
lost.includes(el+1))  
}
  // 그럼 help엔 빌려주는 애가 들어가게 된다. 
  // help의 length만큼 더하면 되나? 그러면 또 중복.. ?
  
  console.log('빌려줄 수 있는 학생:' , help); // 근데 중복이면 못 빌려주니까...reserve에서 걸러야겠다. 
  // 근데 전부 다 빌려줄 필요가 없어.
  
 console.log('빌려야하는 학생:', lost);
  console.log(help.length - lost.length);
// 빌려줄 수 있는 have.push(...help.filter((el)=>!reserve.includes(el) && !have.includes(el)))
  
  console.log(have);
  console.log(have.length);

  return (help.length-lost.length > 0) ? have.length + help.length - lost.length : have.length + help.length;
  
  // 도난당하지도, 빌리지도 않는 사람 수 고려해야해! n을 고려해야해. 
}

solution(5, [2,4], [1,3,5]); // 5
// solution(5, [2,4], [1,4,5]); // 4
solution(3, [3], [1]); // 2
// solution(5, [2,4], [3]);

 

거의 접근한 줄 알았는데ㅠㅠ

너무 복잡하게 간 것 같다.

사과님이 푸신 방법대로 풀었다...

점수는 많이 받지만 씁쓸...

 

function solution(n, lost, reserve) {
 // 비인간적으로 생각하기
  // 애들을 체육복으로 보라...
  
  let all = new Array(n);
  all.fill(1); // 체육복 1개씩 있다고 가정
  
  // 로스트의 0, 1의 값을 인덱스로 삼아서
  for(let i = 0; i< lost.length; ++i) {
    all[lost[i]-1] -= 1;
  }
  
  for(let i = 0; i<reserve.length; ++i) {
    all[reserve[i]-1] += 1;
  }
  console.log(all) 
  // 따란, 이제 몇 개인지 보여~
  
all.forEach((el, idx) => {
           if(el===0){
             if(all[idx-1]===2) {
               all[idx-1]-=1;
               all[idx] += 1;
             } else if(all[idx+1]===2) {
               all[idx+1] -=1;
               all[idx] += 1;
             }
           }
  // forEach 앞에서부터 도니까 all[idx-1]===2 일때부터 돌아야한다. 
  
})
return all.filter((el)=> el >= 1).length;
  
}

위에 체육복 수 더해주는 것도 forEach로 할 수 있다.

아직 forEach 어색...ㅎㅎ 낯가리는 중

 

탐욕법이 뭐지 ?? 

 

탐욕법(이하 '그리디') 알고리즘이란 현재 상황에서 가장 좋은 것(최선의 선택)을 고르는 알고리즘을 말합니다. 그리디 알고리즘은 동적 프로그래밍을 간단한 문제 해결에 사용하면 지나치게 많은 일을 한다는 것을 착안하여 고안되었습니다

 

앞의 선택이 뒤의 문제에 대해 영향을 미치지 않을 때.
전체에 대한 최적해가 부분에 대해서도 최적해일 때

 

라고 합니다... 

 

 

---

멘토님 풀이

 

1. 실패한 경우 - 여기서 정렬을 해줘야 한다. (밑에 메서드로 푼 것처럼...)

function solution(n, lost, reserve) {
  const losted = [...lost];
  // 잃어버린 학생의 원본 정보를 복사한다. 
  
  // 여벌 체육복을 가지고 있는 학생이 체육복을 도난당했는지를 체크한다. 
  // 도난 당했다면, lost와 reserve 배열에 해당 학생의 번호를 삭제한다. 
  lost = lost.filter(student => {
    return reserve.includes(student) === false;
    // lost에도 있고 reserve에도 있는 학생
  })
  reserve = reserve.filter(student => losted.includes(student)===false)
  
  // 전체 학생의 수 - 체육복 잃어버린 학생수
  // === 지금 체육 들을 수 있는 학생의 수 
 let answer = n - lost.length;
  
  for(let i = 0; i < lost.length; ++i) {
    console.log(lost[i]);
    if(reserve.includes(lost[i]-1)){
      // 앞 번호 학생 조회
      reserve.splice(reserve.indexOf(lost[i]-1), 1);
      answer++;
    } else if(reserve.includes(lost[i]+1)) {
reserve.splice(reserve.indexOf(lost[i]+1));
      answer++;
    }
  }
  return answer;
}

2. 메서드 풀기

function solution(n, lost, reserve) {
 const losted = [...lost];
  
  lost = lost.filter(student=> reserve.includes(student)===false).sort((a,b)=>a-b);
  reserve=reserve.filter(student=> losted.includes(student)===false).sort((a,b)=>-b);
  
  return lost.reduce((acc,cur)=> {
    const prev = reserve.indexOf(cur-1); // 앞에 있는 학생의 번호에게서 빌려올 수 있어?
    const next = reserve.indexOf(cur+1); // 뒤에 있는 학생이 여벌 체육복 갖고 있는지?
    // 앞에 있는 학생이 여벌 체육복 갖고 있다면
    if(prev !== -1) {
      reserve.splice(prev,1);
      acc++;
    } else if(next !== -1) {
      reserve.splice(next, 1);
      acc++;
    }
    return acc;
  },n-lost.length)
}

 

너무...난 상상할 수 없어 ㅠ ㅠ ㅠㅠ