[프로그래머스]Greedy -- 체육복(with JS)

장현광·2021년 3월 26일

알고리즘

목록 보기

1/8

첫 번째 시도

function solution(n, lost, reserve) {
    let safe = reserve.filter(el => !lost.includes(el))
    
    for(let i of lost) {
        if(safe.includes(i - 1)) {
            safe.push(i)
        } else if(safe.includes(i + 1)) {
            safe.push(i)
        }
    }
    
    return safe.length
}

결과

문제점

체육복이 2개였다가 빌려줘서 한 개가 된 학생을 걸러내지 못함.

개선

safe 배열에서 체육복을 빌릴수 있는지 판단하였지만, reserve에서 판단을 하고, 성공한 경우 빌려준 학생은 reserve에서 삭제, 빌린 학생은 safe에 추가

두 번째 시도

function solution(n, lost, reserve) {
    let criterion = reserve
    let safe = reserve.filter(el => !lost.includes(el))
    
    for(let i of lost) {
        if(criterion.includes(i - 1)) {
            safe.push(i)
            criterion = criterion.filter(el => el !== i - 1)
        } else if(criterion.includes(i + 1)) {
            safe.push(i)
            criterion = criterion.filter(el => el !== i + 1)
        }
    }
    
    return safe.length
}

결과

문제점

학생을 체육복이 2개이거나 잃어버린 경우만 고려해버림.
처음부터 1개만 있는 학생들을 카운트 하지 않음.

개선

return할 때 전체 학생수에서 체육복이 2개이거나
return에서 전체 학생수 n에서 처음부터 1개이거나 2개였는데 잃어버린 학생 수 만큼 더해준다.

safe.length + n - {(reserve - lost)의 길이 + (lost - reserve)의 길이}

세 번째 시도

function solution(n, lost, reserve) {
    let criterion = reserve
    let safe = reserve.filter(el => !lost.includes(el))
    
    for(let i of lost) {
        if(criterion.includes(i - 1)) {
            safe.push(i)
            criterion = criterion.filter(el => el !== i - 1)
        } else if(criterion.includes(i + 1)) {
            safe.push(i)
            criterion = criterion.filter(el => el !== i + 1)
        }
    }
    
    return safe.length + (n - (reserve.filter(el => !lost.includes(el)).length + lost.filter(el => !reserve.includes(el)).length))
}

를 하고 제출을 해봤더니?

ㅎㅎ;; (^///^)

문제점

케이스를 추가하고 점검해보니 for문에서 lost를 기준으로 하니, 체육복이 2개였다가 잃어버려서 1개가 된 학생들까지 체육복을 빌리는 상황.

또한 2개였는데 1개를 잃어버린 학생들까지 여분이 있는 상황으로 되어있음.

개선

새로운 배열을 만들어 순수하게 0개인 학생들만 모아놓고 for문으로 체육복 빌리도록 하기.
순수하게 2개만 있는 학생들만으로 extra 배열 만들기

네 번째 시도

function solution(n, lost, reserve) {
    let extra = reserve.filter(el => !lost.includes(el))      // 여벌이 있는 학생들
    let safe = reserve.filter(el => !lost.includes(el))       // 체육수업 가능핞 학생들
    let REAL_LOST = lost.filter(el => !reserve.includes(el))  // 체육복 빌려야 하는 학생들
    const ORIGINAL_ONE = (n - (reserve.filter(el => !lost.includes(el)).length + lost.filter(el => !reserve.includes(el)).length)) // 원래 1개였거나, 2개였는데 1개가 된 사람의 수
    
    // REAL_LOST에서 한 명씩 순서대로 빌리기
    for(let i of REAL_LOST) {
        if(extra.includes(i - 1)) {
            safe.push(i)                                // 빌린 학생은 safe로 넣기
            extra = extra.filter(el => el !== i - 1)    // 빌려준 학생은 extra에서 제외
        } else if(extra.includes(i + 1)) {
            safe.push(i)
            extra = extra.filter(el => el !== i + 1)
        }
    }
    
    return safe.length + (n - (reserve.filter(el => !lost.includes(el)).length + lost.filter(el => !reserve.includes(el)).length))
}