[BOJ] 1931 - 회의실 배정

gmelan·2022년 4월 16일
0

알고리즘 트레이닝

목록 보기
12/14

풀어보기

접근

  1. 무조건 종료 시간이 가장 이른 회의를 선택하는 것이 이득이다.
  2. 하지만 그 회의의 시작 시간이 기존에 선택한 회의와 충돌하지 않아야 한다.

이 아이디어들 자체는 그리 어렵지 않게 낼 수 있었으나, 후술하듯이 구현에서 삽질을 하는 바람에 좀 해멨다.

가장 먼저 생각해 낸 것은 주어진 범위 내 최소 종료 시간을 갖는 회의를 찾는 함수를 재귀적으로 호출하는 방법으로, 0<=T<=23110 <= T <= 2^{31} - 1라는 어마무시한 시간의 범위와 O(n2)O(n^2)에 이르는 시간복잡도 덕에 통과에 실패하였다.

코드 1 - 무시무시한 멧집의 코드

from sys import stdin

N = int(stdin.readline())
INT_MAX = 2**32

def search(begin, end):
    global N, INT_MAX, time_max, meetings

    res = 0
    next_begin = begin
    min_end_time = begin

    for i in range(begin, end):
        if meetings[i] < min_end_time:
            min_end_time = meetings[i]
            next_begin = begin
            res += 1
    
    next_end = meetings[next_begin] if meetings[next_begin] != INT_MAX else time_max

    return res + search(next_begin, next_end)

time_max = 0
meetings = [INT_MAX for _ in range(INT_MAX)]

for _ in range(N):
    a, b = tuple(int(i) for i in stdin.readline().rstrip().split())
    if b > meetings[i]:
        meetings[i] = b
    
    if b > time_max:
        time_max = b

print(search(0, meetings[0]))

회의들을 meetings 배열에 meetings[시작 시간] = 종료 시간의 형식으로 저장하여 회의를 시작 시간에 대하여 오름차순으로 정렬시킨 후, 후보군 회의의 시작~종료 시간 범위 내 더 이른 종료 시간을 갖는 회의를 재귀적으로 찾아낸다.

예제 정도는 가볍게 통과할 수 있었지만 회의 시간이 늘거나(=배열 길이 증가), 회의 수가 많아지면(=탐색 후보의 증가) 시간 및 메모리 초과를 내기 일쑤였다.

며칠 고민하다가 결국 질문 검색 게시판에 진입하였고, 큰 깨달음을 얻었다(...).

코드 2 - 정렬하고 탐색하는 코드

from sys import stdin

N = int(stdin.readline())
jobs = [[int(i) for i in stdin.readline().split()] for _ in range(N)]
jobs.sort(key=lambda x:(x[1], x[0]))

count = 0
prev_end = 0

for begin, end in jobs:
    if begin >= prev_end:
        count += 1
        prev_end = end

print(count)

회의 목록이 (1순위: 종료 시각, 2순위: 시작 시각)에 대하여 오름차순으로 정렬되어 있다면 단 하나의 반복문만으로 모든 것을 해결할 수 있다. 우리가 신경쓸 것은 다음 회의가 이전 회의와 겹치는지 확인하는 것 밖에 없다...

시사점

N<=100000이라는 범위에 압도되어(...) 비용이 크다고 생각되는 정렬이라는 방법을 쉽게 적용하지 못했으나, 그것보다 비용이 더 큰 코드만 남발하며 헤메다가 겨우 정답을 찾았다.

소프트웨어를 만지는 것은 부담이 없다. 다른 분야의 경우와는 다르게 실패했을 때의 자원 손실이 사실상 없기 때문이다. 그만큼 다양한 시도를 과격하게 해볼 수 있다는 굉장히 큰 장점을 갖고 있다고 생각한다.
나는 지금 이런 좋은 특성을 잘 활용하고 있는 것일까? 조금 더 과격한 시도를 해봐도 되지 않을까? 도전하면 변화가 생기지만 가만히 있으면 아무것도 일어나지 않는다. 머리만 싸메지 말고 뭐라도 적어서 실행을 해 볼 생각을 해야 하는게 아닌가. 적어도 코딩을 하는 데 있어서는 좀 더 막나가도 될(...) 때가 아닌가 하는 생각이 든다.

0개의 댓글