[Algorithm] 프로그래머스 - 호텔 대실

문제

[프로그래머스] 호텔 대실

 

사용 알고리즘

- 그리디 (Greedy)

해결방법

키 포인트는 다음 2가지

• 시간 데이터를 분으로 변경
• 입실 시간을 기준으로 정렬
• 퇴실 시간을 담는 배열을 통해 필요한 방의 개수를 count

입실 시간을 기준으로 정렬한 배열 sortedT를 가지고 반복문을 돌며, 해당 순서 사람의 끝나는 시간을 finishT 배열에 담는다. finishT 배열은 항상 빠른 시간이 앞에 오도록 오름차순 정렬을 해주고, 반복문이 돌때마다 현재 순서 사람의 입실 시간과 finishT 배열의 가장 빠른 퇴실 시간을 비교해, 퇴실시간이 더 빠른 경우 그 방에 사람을 받을 수 있다는 뜻이므로 finishT 배열에서 해당 시간을 제거한다.

문제 예시 이미지

finishT에 담기는 데이터를 순서대로 보면 다음과 같다.

finishT = [19:20]

finishT = [15:20, 19:20]

finishT = [15:20, 17:00, 19:20]

finishT = [17:00, 18:20, 19:20]

finishT = [18:20, 19:20, 21:20]

소스코드

사용언어 : javascript

// 입실 시간 기준으로 sort
// 퇴실 시간 = 퇴실 시간 + 10분
function solution(book_time) {
    let finishT = []; // 끝나는 시간을 담는 배열
    let sortedBT = book_time.sort();

    sortedBT.forEach((t) => {
        let inTime = t[0].split(":");
        let inTimeMin = inTime[0] * 60 + parseInt(inTime[1]);
        let outTime = t[1].split(":");
        let outTimeMin = outTime[0] * 60 + parseInt(outTime[1]) + 10;
        
        if (finishT[0] > 0 && inTimeMin >= finishT[0]) { // 지금 온 사람이 가장 빨리 끝나는 방에 바로 들어갈 수 있는 경우
            finishT.splice(finishT.indexOf(finishT[0]), 1);
        } 
        finishT.push(outTimeMin);
        finishT.sort(function(a, b){ return a-b; }); // 항상 가장 빨리 끝나는 순서로 정렬
    });
    return finishT.length;
}

sort 함수

* 자바스크립의 sort 함수는 배열을 문자열로 간주하고 정렬을 한다. [b, a, c] 의 경우, sort 하면 [a, b, c]로 잘 정렬해줌.

* 숫자의 경우도 문자열로 변환해서 정렬을 하는데, [90, 110, 100] 이면 ["90", "110", "100"] 으로 인식해 정렬한다.

 

때문에, 숫자 타입을 정렬하고 싶은 경우 compare 함수를 선언해주어야 하는데, sort 함수의 parameter 부분에 선언해주면 된다.

arr.sort([compareFunction])

 

한줄평

javascript로 시간을 분으로 바꾸는게 너무 귀찮은 것 같다. 더 쉬운 방법 없나 ?

 

 

참고 블로그

https://mrb18.tistory.com/entry/%EC%9E%90%EC%A3%BC-%ED%97%B7%EA%B0%88%EB%A6%AC%EB%8A%94-%EC%9E%90%EB%B0%94%EC%8A%A4%ED%81%AC%EB%A6%BD%ED%8A%B8-if%EB%AC%B8%EC%9C%BC%EB%A1%9C-undefined-%EC%B2%B4%ED%81%AC%ED%95%A0%EB%95%8C-%EB%B2%88%EC%99%B8-Null%EC%B2%B4%ED%81%AC

https://ko.javascript.info/comparison

https://siyoon210.tistory.com/148