[코딩테스트 준비]자바스크립트 그리드 알고리즘 코딜리티 연습 javascript algorithm codility greedy

그리드 알고리즘

 

회의시간 배정, 현금으로 거스름돈 걸러주기 등 관련된 문제가 나오면 그리드 문제라고 생각하면 된다.

 

핵심은 회의시간의 경우 끝 시간이 가장 가까운 시간 순으로 정렬

 

거스름돈의 경우 가장 큰 단위 부터 정렬 해야 된다.

 

이렇게 특정 기준으로 먼저 정렬해놓고 다음 기준은 나중에 생각하는 개념이다. 

 

코딜리티 팁

영어로 되어 있으니깐 확실히 소소한 기준을 읽기가 어렵다.

1. 코딜리티 처음부터 정렬이 되어 있다
2. 1점이 겹처도 되는지 안되는지 꼭 확인해야 된다
3. 빈 배열이 들어오는 경우에 대한 예외 처리도 하자

function solution(A, B) {
    const meeting = B.map((end, index) => {
        return [A[index], end]
    })

    meeting.sort((a, b) => {
        if (a[1] === b[1]) {
            return a[0] - b[0]
        } else {
            return a[1] - b[1]
        }

    })

    let count = 1
    let time = meeting[0][1]

    for(et of meeting){
        if(time < et[0]){
            ++count
            time = et[0]
        }
    }
    return count
}