[프로그래머스] JavaScript Lv2 - 호텔 대실(155651)

개요

문제 이름: 호텔 대실 (155651)
문제 링크: https://school.programmers.co.kr/learn/courses/30/lessons/155651
플랫폼: 프로그래머스
알고리즘 분류: 그리디
소요 시간: 4시간 20분

 

문제 전문

설명

제한사항

입출력

 

문제 풀이

해설

호텔을 운영 중인 코니는 최소한의 객실만을 사용하여 예약 손님들을 받으려고 합니다. 한 번 사용한 객실은 퇴실 시간을 기준으로 10분간 청소를 하고 다음 손님들이 사용할 수 있습니다.

 

예약 시각이 문자열 형태로 담긴 2차원 배열 book_time이 매개변수로 주어질 때, 코니에게 필요한 최소 객실의 수를 반환하는 함수를 완성하는 것이 문제의 목표입니다.

 

문제 해결을 위한 접근 방식은 아래와 같습니다.

1. 시간 표현 변환: 주어진 시각 형식(HH:MM)을 더 다루기 쉬운 형태(분 단위)로 변환합니다.
2. 예약 시간 정렬: 시작 시각을 기준으로 예약 시간을 오름차순으로 정렬합니다. 이렇게 하면 시간 순서대로 예약을 처리할 수 있습니다.
3. 예약 처리: 정렬된 예약 시간을 하나씩 확인하면서, 해당 예약을 처리할 수 있는 빈 객실을 찾습니다.
4. 기존에 사용 중인 객실 중 하나가 해당 예약 시각에 사용 가능한 경우, 그 객실을 할당합니다.
5. 사용 가능한 객실이 없는 경우, 새로운 객실을 추가합니다.
6. 최종 객실 수 반환: 모든 예약을 처리한 후, 사용된 총 객실 수를 반환

 

시도

1차 시도  (실패)

//1차 시도 - 실패
function solution(book_time) {
	function timeToMinutes(time) {
		const [hours, minutes] = time.split(":").map(Number);
		return hours * 60 + minutes;
	}

	const bookings = book_time.map(([start, end]) => [timeToMinutes(start), timeToMinutes(end) + 10]);

	let roomCount = 0;

	for (let i = 0; i < bookings.length; i++) {
		let overlapping = 1;

		for (let j = 0; j < bookings.length; j++) {
			if (i !== j) {
				if (bookings[i][0] < bookings[j][1] && bookings[j][0] < bookings[i][1]) {
					overlapping++;
				}
			}
		}

		roomCount = Math.max(roomCount, overlapping);
	}

	return roomCount;
}

이 접근 방식은 각 예약에 대해 겹치는 모든 예약을 찾아 최대 겹침 수를 계산합니다. 하지만 이 방법은 일부 테스트 케이스에서 실패합니다...

 

시간 복잡도가 비효율적인 것도 문제이지만, 곰곰히 생각해보면 실제 객실 할당 과정을 시뮬레이션하지 않아 정확한 최소 객실 수를 구하지 못하는 문제가 있습니다.

1. timeToMinutes 함수는 "HH:MM" 형식의 시각 문자열을 분 단위의 숫자로 변환합니다.
   1. split 메서드로 시각 문자열을 ":" 기준으로 분리하여 시와 분을 추출합니다.
   2. map(Number)를 사용하여 추출한 시와 분을 숫자로 변환합니다.
   3. 시를 60과 곱하고 분을 더하여 총 분 단위의 시각을 계산합니다.
2. bookings 배열은 주어진 book_time 배열의 각 예약 시각을 분 단위로 변환하여 저장합니다.
   1. 예약 종료 시각에는 10분의 청소 시간을 추가합니다.
3. 이중 반복문을 사용하여 각 예약마다 겹치는 예약의 수를 계산합니다.
   1. 현재 예약(i)과 다른 모든 예약(j)을 비교합니다.
   2. 두 예약이 겹치는 경우, overlapping 변수를 증가시킵니다.
4. roomCount는 최대 겹치는 예약 수를 저장합니다.
   1. Math.max 함수를 사용하여 현재까지의 roomCount와 현재 예약의 overlapping 값 중 큰 값을 선택합니다.
5. 최종적으로 계산된 roomCount를 반환합니다.

 

시간 복잡도 및 공간 복잡도

• 시간 복잡도:  O(n^2)
  • 여기서 n은 예약의 수입니다.
• 공간 복잡도: O(n)
  • 변환된 예약 정보를 저장하는 배열 때문입니다.

 

2차 시도  (성공)

//2차 시도 - 성공
function solution(book_time) {
	// 시간을 분으로 바꾸는 함수
	function changeTimeToMinutes(time) {
		// 시간 문자열을 : 기준으로 쪼개서 시간과 분을 분리
		const splitTime = time.split(":");
		const hours = parseInt(splitTime[0]);
		// 시간을 숫자로 변환
		const minutes = parseInt(splitTime[1]);
		// 분을 숫자로 변환

		// 시간을 분으로 변환하고 기존 분을 더함
		return hours * 60 + minutes;
	}

	// 모든 예약 시간을 분으로 바꾸고 새로운 배열 만들기
	const changedBookings = book_time.map(function (booking) {
		return {
			startTime: changeTimeToMinutes(booking[0]),
			// 시작 시간을 분으로 변환
			endTime: changeTimeToMinutes(booking[1]) + 10,
			// 종료 시간을 분으로 변환하고 청소 시간 10분 추가
		};
	});

	// 예약들을 시작 시간 순서대로 정렬
	changedBookings.sort(function (a, b) {
		return a.startTime - b.startTime;
	});

	const usedRooms = [];
	// 사용 중인 방들의 종료 시간을 저장할 배열

	// 모든 예약에 대해 반복
	for (let i = 0; i < changedBookings.length; i++) {
		const currentBooking = changedBookings[i];
		let foundEmptyRoom = false;
		// 빈 방을 찾았는지 표시하는 변수

		// 이미 사용 중인 방들을 확인
		for (let j = 0; j < usedRooms.length; j++) {
			// 만약 방의 사용 종료 시간이 현재 예약의 시작 시간보다 이르다면
			if (usedRooms[j] <= currentBooking.startTime) {
				usedRooms[j] = currentBooking.endTime;
				// 해당 방의 사용 종료 시간을 현재 예약의 종료 시간으로 업데이트
				foundEmptyRoom = true;
				// 빈 방을 찾았다고 표시
				break;
				// 방을 찾았으니 더 이상 찾지 않아도 됨
			}
		}

		// 만약 빈 방을 찾지 못했다면
		if (!foundEmptyRoom) {
			usedRooms.push(currentBooking.endTime);
      // 새로운 방을 추가하고 현재 예약의 종료 시간을 저장
		}
	}

	// 총 사용된 방의 개수 반환
	return usedRooms.length;
}

해당 방식은 호텔 예약 시간을 분 단위로 변환하고 시작 시간순으로 정렬한 뒤, 각 예약에 대해 가능한 가장 빠른 시간에 비는 객실을 할당하거나 새 객실을 추가함으로써, 그리디 접근법을 통해 모든 예약을 수용하는 최소한의 객실 수를 효율적으로 계산하는 방식입니다.

1. changeTimeToMinutes 함수는 "HH:MM" 형식의 시각 문자열을 분 단위의 숫자로 변환합니다.
   1. split 메서드로 시각 문자열을 ":" 기준으로 분리하여 시와 분을 추출합니다.
   2. parseInt 함수를 사용하여 추출한 시와 분을 숫자로 변환합니다.
   3. 시를 60과 곱하고 분을 더하여 총 분 단위의 시각을 계산합니다.
2. changedBookings 배열은 주어진 book_time 배열의 각 예약 시각을 분 단위로 변환하여 저장합니다.
   1. map 메서드를 사용하여 각 예약의 시작 시각과 종료 시각을 분 단위로 변환합니다.
   2. 종료 시각에는 10분의 청소 시간을 추가합니다.
3. changedBookings 배열을 시작 시각을 기준으로 오름차순 정렬합니다.
   1. sort 메서드를 사용하여 예약들을 시작 시각 순서대로 정렬합니다.
4. usedRooms 배열은 현재 사용 중인 객실들의 사용 종료 시각을 저장합니다.
5. 정렬된 예약들을 순회하며 각 예약을 처리합니다.
   1. 현재 예약의 시작 시각이 usedRooms 배열에 저장된 객실들의 사용 종료 시각보다 늦은 경우, 해당 객실을 사용할 수 있습니다.
      1. 해당 객실의 사용 종료 시각을 현재 예약의 종료 시각으로 업데이트합니다.
   2. 사용 가능한 객실이 없는 경우, 새로운 객실을 usedRooms 배열에 추가하고 현재 예약의 종료 시각을 저장합니다.
6. 최종적으로 usedRooms 배열의 길이를 반환하여 필요한 총 객실 수를 나타냅니다.

 

시간 복잡도 및 공간 복잡도

• 시간 복잡도:  O(n log n)
  • 예약 시각을 분 단위로 변환하고 정렬하는 과정에서 O(n log n)의 시간이 소요됩니다.
  • 예약을 처리하는 과정에서는 최악의 경우 O(n^2)의 시간이 걸릴 수도 있을 것 같지만... 일반적으로는 O(n)에 가깝습니다.
• 공간 복잡도: O(n)
  • changedBookings 배열과 usedRooms 배열에 예약 정보를 저장하므로 O(n)의 추가 공간이 필요합니다.