[코딩테스트]백준 - 회의실배정

회의실배정

문제

한 개의 회의실이 있는데 이를 사용하고자 하는 N개의 회의에 대하여 회의실 사용표를 만들려고 한다. 각 회의 I에 대해 시작시간과 끝나는 시간이 주어져 있고, 각 회의가 겹치지 않게 하면서 회의실을 사용할 수 있는 회의의 최대 개수를 찾아보자. 단, 회의는 한번 시작하면 중간에 중단될 수 없으며 한 회의가 끝나는 것과 동시에 다음 회의가 시작될 수 있다. 회의의 시작시간과 끝나는 시간이 같을 수도 있다. 이 경우에는 시작하자마자 끝나는 것으로 생각하면 된다.

입력

첫째 줄에 회의의 수 N(1 ≤ N ≤ 100,000)이 주어진다. 둘째 줄부터 N+1 줄까지 각 회의의 정보가 주어지는데 이것은 공백을 사이에 두고 회의의 시작시간과 끝나는 시간이 주어진다. 시작 시간과 끝나는 시간은 231-1보다 작거나 같은 자연수 또는 0이다.

출력

첫째 줄에 최대 사용할 수 있는 회의의 최대 개수를 출력한다.

예제 입력 1

11
1 4
3 5
0 6
5 7
3 8
5 9
6 10
8 11
8 12
2 13
12 14

예제 출력 1

4

힌트

• (1,4), (5,7), (8,11), (12,14) 를 이용할 수 있다.

출처

• 빠진 조건을 찾은 사람: andy627
• 데이터를 추가한 사람: kimchangyoung rosedskim

알고리즘 분류

• 그리디 알고리즘

해결한 코드

var fs = require('fs');
var input = fs.readFileSync('/dev/stdin').toString().trim().split('\n');
// var input = fs.readFileSync(__dirname + '/stdin.txt').toString().replace(/\r/g, "").trim().split('\n');
var n = parseInt(input[0])
var meetings = []
for(var i=1; i<input.length; i++){
    var meeting = input[i].split(' ').map(e=> e/1)
    meetings.push({start:meeting[0], end:meeting[1]})
}
meetings.sort((a, b)=> {
    if(a.end - b.end === 0 ){
        return a.start-b.start
    } else {
        return a.end - b.end
    }
})
var answer = [meetings[0]]
meetings.shift()
meetings.forEach(function(meeting){
    if(meeting.start >= answer[answer.length-1].end){
        answer.push(meeting)
    }
})
console.log(answer.length)

알고리즘

1. 회의가 끝나는 시간이 빠른 순서대로 오름차순 정렬한다.

📌 단, 끝나는 시간이 같은 것들이 있다면, 회의가 시작하는 시간이 빠른 것부터 먼저 오도록 정렬한다.

2. 가능한 회의들을 저장할 배열을 선언한다.

나는 answer라는 배열을 선언했다.

3. answer 안에 첫번째 회의를 넣는다.

첫번째 회의는 끝나는 시간이 가장 빠른 회의이므로 무조건 하게 되어있기 때문이다.

4. 첫번째 회의를 제외한 나머지 회의들을 차례대로 조건에 맞는지 확인한다.

• 회의가 시작하는 시간은 이전 회의가 끝나는 시간보다 같거나 커야 한다.
  👉🏻 회의 시작 시간이 answer의 마지막 원소의 끝나는 시간보다 크거나 같은지 확인한다.
  👉🏻 크거나 같으면 answer에 넣는다.

5. answer 배열의 길이를 출력한다.

처음 구상한 코드 - 메모리초과

var fs = require('fs');
var input = fs.readFileSync('/dev/stdin').toString().trim().split('\n');
// var input = fs.readFileSync(__dirname + '/stdin.txt').toString().replace(/\r/g, "").trim().split('\n');
var n = parseInt(input[0])
var meetings = []
for(var i=1; i<input.length; i++){
    var meeting = input[i].split(' ').map(e=> e/1)
    meetings.push(meeting)
}
meetings.sort((a, b)=> a[1]-b[1])

var answer = [0]

for(var i=0; i<meetings.length; i++){
    var currentStart = meetings[i]
    var result = [currentStart]
    findMaxMeetings(currentStart, i, result, meetings)
}

console.log(answer[0])


function findMaxMeetings(currentStart, index, result, meetings){
    if(meetings.every(e=> e[0]<currentStart[1])){
        if(result.length >= answer[0])
        answer[0] = result.length
        return 
    }
    var newMeetings = meetings.slice()
    newMeetings.splice(index, 1)
    for(var i=0; i<newMeetings.length; i++){
        var next = newMeetings[i]
        if(next[0] >= currentStart[1]){
            result.push(next)
            findMaxMeetings(next, i, result, newMeetings)
            result.pop()
        }

    }
}

처음 구상한 알고리즘

백트래킹을 활용해 풀려고 했다.

회의 = [
  [ 1, 4 ],   [ 3, 5 ],
  [ 0, 6 ],   [ 5, 7 ],
  [ 3, 8 ],   [ 5, 9 ],
  [ 6, 10 ],  [ 8, 11 ],
  [ 8, 12 ],  [ 2, 13 ],
  [ 12, 14 ]
]

이렇게 입력이 들어오면, 일단 끝나는 시간에 맞춰 정렬을 하고, 정렬된 회의 배열들을 가지고...

[ 1, 4 ] => [ 5, 7 ] => [ 8, 11 ] => [ 12, 14 ]

이렇게 재귀로 탐색하다가 다 탐색했으면 탐색한 배열들의 갯수를 저장한 후 return 해서 돌아오고,

[ 1, 4 ] => [ 5, 7 ] => [ 8, 12 ] => [ 12, 14 ]

이렇게 다음 재귀로 탐색하고..
이런식으로 백트래킹으로 구현해보았으나..

🤦🏻‍♀️ 역시나 메모리 초과에 부딪혔다.

입력 예시는 어찌어찌 잘 계산되는 것 같은데, 사실 반례가 나올 수도 있다...
(혹시나 하는 마음에 제출해봤는데 메모리 초과 떠서 걍 포기한 코드기 때문에 장담 못함)
또 지금 보니까 정렬도 끝나는 시간에만 맞춰 정렬시켜서 통과하지 못했을 것 같다.
그저 재귀를 또한번 연습했다는 것에 의의를 두기로 했다.

두번째로 구상한 코드 - 시간초과

var fs = require('fs');
var input = fs.readFileSync('/dev/stdin').toString().trim().split('\n');
// var input = fs.readFileSync(__dirname + '/stdin.txt').toString().replace(/\r/g, "").trim().split('\n');
var n = parseInt(input[0])
var meetings = []
for(var i=1; i<input.length; i++){
    var meeting = input[i].split(' ').map(e=> e/1)
    meetings.push(meeting)
}
meetings.sort((a, b)=> a[1]-b[1])

var start = meetings[0]
var index = 0
var count = 1
while(true){
    var flag = false
    for(var i=index; i<meetings.length; i++){
        var next = meetings[i]
        if(next[0]>=start[1]){
            flag = true
            start = next
            count++
            index = i
            break
        }
    }
    if(!flag){
        break
    }
}
console.log(count)

두번째로 구상한 알고리즘

이중 반복문을 사용했다.

회의 = [
  [ 1, 4 ],   [ 3, 5 ],
  [ 0, 6 ],   [ 5, 7 ],
  [ 3, 8 ],   [ 5, 9 ],
  [ 6, 10 ],  [ 8, 11 ],
  [ 8, 12 ],  [ 2, 13 ],
  [ 12, 14 ]
]

이렇게 입력이 들어오면, (처음 알고리즘과 마찬가지로) 끝나는 시간에 맞춰 오름차순으로 정렬한 후

start = [ 1, 4 ]

회의의 가장 첫번째 원소를 start라는 변수에 할당하고

index = 0
count = 1

첫번째 원소의 인덱스는 0이니까, 0을 index라는 변수에 할당하고, 첫번째 회의는 무조건 진행하니까 count라는 변수에 1을 할당하여 선언하였다.

그리고 나머지 회의들에 대해서 반복문을 돌리는 데,

현재 index = 0이니까 회의 배열을 인덱스 0부터 ~ 끝까지 탐색하면서
✔ 회의 시작 시간이 start의 끝나는 시간보다 크거나 같은지 체크

• 만약 크거나 같다면
  👉🏻 해당 회의를 start로 새로 지정
  👉🏻 count 추가
  👉🏻 index를 현재 회의의 i값으로 지정
  🚩 flag = true로 바꾸기

• 만약 위 조건에 맞는 회의가 없다면
  🚩 flag는 false
  👉🏻 반복문을 종료한다.

그렇게 계산되어온 count를 출력한다.

하지만 이미 정렬에서 문제가 한번 발생하고,
무엇보다 시간초과가 나면서 '아.. 2중 반복문도 역시 안되는군..' 했다.
여러 방법을 시도한 것에 한번 더 의의를 두며 이 코드도 짜이찌엔..! 🖐🏻

사실 입력으로 들어오는 N의 수가 커서 재귀랑 이중 반복문은 어려울 거라고 으레 생각하긴 했다 ㅜㅜ
하지만 뾰족한 알고리즘이 생각나지 않아 일단 저질러 봤던 두 시행착오..... 두 시행착오 덕분에 통과 가능한 알고리즘도 구상할 수 있었다 !