탐욕법(greedy) 알고리즘이 제일 쉬운거라는데...? 이거 맞아??😂😂😂😂😂
👉 문제 풀러가기 : https://school.programmers.co.kr/learn/courses/30/lessons/42862?language=javascript
점심시간에 도둑이 들어, 일부 학생이 체육복을 도난당했습니다. 다행히 여벌 체육복이 있는 학생이 이들에게 체육복을 빌려주려 합니다. 학생들의 번호는 체격 순으로 매겨져 있어, 바로 앞번호의 학생이나 바로 뒷번호의 학생에게만 체육복을 빌려줄 수 있습니다. 예를 들어, 4번 학생은 3번 학생이나 5번 학생에게만 체육복을 빌려줄 수 있습니다. 체육복이 없으면 수업을 들을 수 없기 때문에 체육복을 적절히 빌려 최대한 많은 학생이 체육수업을 들어야 합니다.
전체 학생의 수 n, 체육복을 도난당한 학생들의 번호가 담긴 배열 lost, 여벌의 체육복을 가져온 학생들의 번호가 담긴 배열 reserve가 매개변수로 주어질 때, 체육수업을 들을 수 있는 학생의 최댓값을 return 하도록 solution 함수를 작성해주세요.
제한사항
입출력 예
n | lost | reserve | return |
---|---|---|---|
5 | [2, 4] | [1, 3, 5] | 5 |
5 | [2, 4] | [3] | 4 |
3 | [3] | [1] | 2 |
function solution(n, lost, reserve) {
//Array를 n만큼 생성한 뒤 1로 초기화 시켜줌
//[1,1,1,1,1]
const students = new Array(n).fill(1)
//최종적으로 체육복을 가지고 있는 학생 수 카운팅하는 변수
let result = 0
for(let i = 0; i < lost.length; i++){
//lost[i]-1과 lost[i-1]을 헷갈리지말자
//lost[i]-1은 배열의 요소 값을 -1 시키는것이고, lost[i-1]은 배열 index를 -1 시킴
//students[lost[i]-1]--와 students[lost[i]-1]-1도 헷갈리지말자
//students[lost[i]-1]--은 감소 시킨 값을 다시 할당해주는 방면 students[lost[i]-1]-1은 students에 -1을 하지만 할당을 하지않고 그냥 끝낸다
//따라서 students[lost[i]-1]--을 하거나 students[lost[i]-1]-=1을 하는게 좋음
students[lost[i]-1]--
}
for(let i = 0; i < reserve.length; i++){
//배열의 인덱스는 0부터 시작하고 우리가 찾는 애는 1부터 시작하니까 i-1을 해야됨
//reserve[i]+1을하면 2,4,6이 되겠쥬?
//그럼 엉뚱하게 결과가 나옴!
//[ 1, 0, 2, 0, 2, <1 empty item>, NaN ] 요렇게!
students[reserve[i]-1]++
}
//현재 students는 [2,0,2,0,2]인 상태
for(let i = 0; i < students.length; i++){
//이제 0인 학생에게 여유분 가지고 있는 애한테 노나주기
if(students[i] === 0){
//i가 0이면 없는애고 [i-1]이나 [i+1]이 === 2면 앞뒤 학생이 2개 가지고있는거니까 노나줌
//그래서 students[i]에는 ++ 해주고 앞이나 뒤는 --해주는것
if(students[i-1] === 2){
students[i]++
students[i-1]--
} else if(students[i+1] === 2){
students[i]++
students[i+1]--
}
}
}
//이제 잘 나눠가졌는지 확인하는 단계
students.forEach(num => num > 0 && result++)
//forEach는 for문처럼 return을 안해서 result를 최종적으로 return해줘야함
return result
}
console.log(solution(5,[2, 4],[1, 3, 5])) //5