그리디 - 결혼식, 강의실 배정

문제 - 결혼식

현수는 다음 달에 결혼을 합니다.

현수는 결혼식 피로연을 장소를 빌려 3일간 쉬지 않고 하려고 합니다.

피로연에 참석하는 친구들 N명의 참석하는 시간정보를 현수는 친구들에게 미리 요구했습니다.

각 친구들은 자신이 몇 시에 도착해서 몇 시에 떠날 것인지 현수에게 알려주었습니다.

현수는 이 정보를 바탕으로 피로연 장소에 동시에 존재하는 최대 인원수를 구하여 그 인원을 수용할 수 있는 장소를 빌리려고 합니다. 여러분이 현수를 도와주세요.

만약 한 친구가 오는 시간 13, 가는시간 15라면 이 친구는 13시 정각에 피로연 장에 존재하는 것이고 15시 정각에는 존재하지 않는다고 가정합니다.

 

▣ 입력설명

첫째 줄에 피로연에 참석할 인원수 N(5<=N<=100,000)이 주어집니다.

두 번째 줄부터 N줄에 걸쳐 각 인원의 오는 시간과 가는 시간이 주어집니다.

시간은 첫날 0시를 0으로 해서 마지막날 밤 12시를 72로 하는 타임라인으로 오는 시간과 가 는 시간이 음이 아닌 정수로 표현됩니다.

 

▣ 출력설명

첫째 줄에 피로연장에 동시에 존재하는 최대 인원을 출력하세요.

 

▣ 입력예제 1

5

14 18

12 15

15 20

20 30

5 14

 

▣ 출력예제 1

2

 

---

📝풀이과정

내가 구하고 싶은 것은 피로연 장소에 동시에 존재하는 최대 인원수이다.

동시에 존재하는 최대 인원수를 구하기 위해서는 특정 시간에 존재하는 인원 수의 최댓값을 구하면 된다.

위의 예시를 토대로 타임라인을 그려보자.

 

 

 

누군가는 특정 시간에 오고 누군가는 갈 것이다.

그 특정 시간 즉, 누군가 오거나 가는 이벤트가 발생하는 시점에 인원이 몇 명 있는지를 각각 구해 최댓값을 구하면 되는 것이다. 

따라서 입력 데이터를 다음과 같이 변형할 것이다.

 

 

 

s는 오는 시간을 의미하고, e는 가는 시간을 의미한다.

그리고 시간을 기준으로 오름차순을 정리해 타임라인을 완성하면 다음과 같다.

 

 

 

5시에 누군가 온다. 이벤트가 발생했다. 따라서 피로연에 참석한 인원수를 하나 더해준다.

14시에는 누군가 떠난다. 마찬가지로 이벤트가 발생했다. 누군가 떠났으므로 인원수를 하나 빼준다.

이 과정을 반복하면 된다.

단, 여기서 주의할 점은 시간대가 똑같지만 이벤트가 다른 경우가 존재한다.

예를 들어 14시에 누군가는 떠나지만 누군가는 오는 시간이다. 이런 경우에는 어떻게 정렬을 해야할까?

이때는 떠나는 것부터 먼저 정렬을 해줘야한다. 오는 것부터 정렬을 하게 되면 인원수의 최댓값이 다르게 나온다.

 

코드

function solution(times) {
  let result = Number.MIN_SAFE_INTEGER;
  let cnt = 0;
  const timelines = [];
  times.forEach((time) => {
    timelines.push([time[0], 's']);
    timelines.push([time[1], 'e']);
  });
  timelines.sort((a, b) => {
    if (a[0] === b[0]) {
      if (a[1] < b[1]) return -1;
      if (a[1] > b[1]) return 1;
    }
    return a[0] - b[0];
  });
  timelines.forEach(([time, event]) => {
    if (event === 's') cnt += 1;
    else cnt -= 1;
    result = Math.max(result, cnt);
  });

  return result;
}

let arr = [
  [14, 18],
  [12, 15],
  [15, 20],
  [20, 30],
  [5, 14],
];
console.log(solution(arr));

 

---

문제 -  강의실 배정

백준 11000번

 

문제

수강신청의 마스터 김종혜 선생님에게 새로운 과제가 주어졌다. 

김종혜 선생님한테는 Si에 시작해서 Ti에 끝나는 N개의 수업이 주어지는데, 최소의 강의실을 사용해서 모든 수업을 가능하게 해야 한다. 

참고로, 수업이 끝난 직후에 다음 수업을 시작할 수 있다. (즉, Ti ≤ Sj 일 경우 i 수업과 j 수업은 같이 들을 수 있다.)

수강신청 대충한 게 찔리면, 선생님을 도와드리자!

입력

첫 번째 줄에 N이 주어진다. (1 ≤ N ≤ 200,000)

이후 N개의 줄에 Si, Ti가 주어진다. (0 ≤ Si < Ti ≤ 109)

출력

강의실의 개수를 출력하라.

예제 입력 1

3
1 3
2 4
3 5

예제 출력 1

2

 

---

📝풀이과정

문제를 보자마자 결혼식 문제와 비슷한 유형이라는 감이 왔다.

따라서 위의 문제와 똑같이 타임라인을 만들고 시간의 순서대로 오름차순 정렬을 한 다음에 강의가 시작하면 강의실 갯수를 늘려주었다. 만일 강의가 시작했는데 이전 타임라인에 끝난 시간과 동일하다면 갯수를 세지 않았다.

let [n, ...arr] = require('fs').readFileSync('./input.txt').toString().trim().split('\n');
arr = arr.map((e) => e.split(' ').map(Number));

function solution(arr) {
  const timelines = [];
  let cnt = 0;
  let end = -1;
  arr.forEach(([start, end]) => {
    timelines.push([start, 's']);
    timelines.push([end, 'e']);
  });
  timelines.sort((a, b) => a[0] - b[0]);
  timelines.forEach((timeline) => {
    if (timeline[1] === 's') {
      if (end !== timeline[0]) cnt++;
    } else end = timeline[0];
  });

  return cnt;
}

console.log(solution(arr));

 

하지만 결과는 실패했다.

왜 실패했는지 반례를 찾지 못해 질문 게시판을 찾아보며 사례를 구했다.

 

✋반례

입력 예제가 다음과 같다.

8
1 8
9 16
3 7
8 10
10 14
5 6
6 11
11 12

 

내가 구하고 싶은 것은 모든 수업이 가능한 최소 강의실 갯수이다.

따라서 최소 강의실 갯수를 가질 수 있도록 타임라인을 구해보면 다음과 같다.

1 - 8 - 10 - 14

5 - 6 - 11 - 12

3 - 7 - 9 - 16

 

이렇게 총 3개가 나와야한다. 하지만 내 코드대로 예제를 집어넣으면 4개라는 오답이 나온다.

이유는 내 코드대로 타임라인을 그려보면 다음과 같이 나온다.

1 - 8 - 10 - 14

5 - 6 - 11 - 12

3 - 7

9 - 16

 

최소 강의실을 구하기 위해서는 3 - 7 과 9 - 16을 하나로 합쳐 한 개의 강의실에서 강의를 진행해야한다.

하지만 나의 코드에서는 강의가 시작할 때마다 하나씩 강의실의 갯수를 늘려갔고, 연달아 강의를 하는 것이 아니면 새로운 강의가 시작할 때마다 강의실의 갯수를 늘렸다.

---

그렇다면 어떻게 해결할 수 있을까?

결혼식 문제와 똑같게 매 시간대에 사용하는 강의실의 갯수를 구한 후 그 최댓값을 구하면 된다.

특정 시간에 강의실을 최대로 사용한다면 적어도 그만큼의 강의실을 확보해야하기 때문이다.

 

코드

// 11000
let [n, ...arr] = require('fs').readFileSync(0).toString().trim().split('\n');
arr = arr.map((e) => e.split(' ').map(Number));

function solution(arr) {
  const timelines = [];
  let cnt = 0;
  let result = Number.MIN_SAFE_INTEGER;
  arr.forEach(([start, end]) => {
    timelines.push([start, 's']);
    timelines.push([end, 'e']);
  });
  timelines.sort((a, b) => {
    if (a[0] === b[0]) {
      if (a[1] < b[1]) return -1;
      if (a[1] > b[1]) return 1;
    }
    return a[0] - b[0];
  });
  timelines.forEach((timeline) => {
    if (timeline[1] === 's') cnt++;
    else cnt--;
    result = Math.max(result, cnt);
  });

  return result;
}

console.log(solution(arr));

 

---

😊느낀점

문제는 다르지만 같은 풀이방법으로 해결할 수 있었다.

처음 강의실 배정 문제를 접근할 때 결혼식처럼 풀 수 있겠다는 감이 왔지만 막상 시도해보니 잘 풀리지 않아서 당황했다.

비슷한 유형이라는 것은 파악할 수 있지만 문제를 구현하는 것에 부족함이 있다는 것을 느꼈다.

다양한 문제를 풀어보며 구현력을 높이고 유형에 더 익숙해져야겠다는 생각이 들었다.