백준 파이썬 1931번 회의실 배정 (Today I Learn 2024.12.12)

백준 파이썬 공부 2024.12.12
1931번 회의실 배정 (골드 5)

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

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

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

4. 문제 풀이
1) 1번 풀이

회의의 시작시간과 종료시간을 노드로 놓고,
최대 길이의 경로를 찾는 문제 >> BFS 사용

- 다만 그 과정에서 역순(4시 > 1시)은 불가능
>> 연결된 노드들 중 현재 노드보다 커야함

 next_node > node

- 중간에 끊겨도 이후의 시간에서 다시 경로를 탐색해야 함
>> queue가 빈다면, 회의가 있는 시간까지 +1 하여 queue에 추가

while not(queue): 
	node += 1
if meeting[node]:
	queue.append(node)
break

- 그리고, 회의의 최대 개수 이므로, 긴 회의 하나보다, 짧은 회의 여러번으로 경로 지정해야함
>> meeting[node] 에 저장된 노드 중, node보다 크면서, 가장 작은 노드로 이동
>> 연결된 노드들을 정렬한다. meeting[i].sort() or 연결된 노드 하나씩 비교

# 연결 노드 정렬 근데 이건 시간제한 걸릴것 같음
for i in range(2**31 - 1):
meeting[i].sort()
for next_node in meeting[node]:
	if next_node > node:
		queue.append(next_node)
break

# 하나씩 비교
nn = 2**23-1
for next_node in meeting[node]:
	if next_node > node:
		nn = min(nn, next_node)
		queue.append(nn)

>> 코드1. 메모리 초과

n = int(input())
meeting = [[] for i in range(2**31)]

for i in range(n):
    st, et = map(int, input().split())
    meeting[st].append(et)
    meeting[et].append(st)

def BFS(start):
    queue = deque()
    queue.append(start)
    cnt = 0
    
    while queue:
        node = queue.popleft()
        cnt += 1
        
        nn = 2**31
        for next_node in meeting[node]:
            if next_node > node:
                nn = min(nn, next_node)
        if nn < 2**31:
            queue.append(nn)
        
        while not queue:
            node += 1
            if meeting[node]:
                queue.append(node)
                break
    return cnt

print(BFS(1))

이렇게 하는게 아닌 듯

숫자와 노드가 너무 많기에 전체 노드를 돌아보며 경로를 찾는 방법은 알맞지 않는 듯 하다.
그렇다면, 적제 적소에 맞는 노드를 선택해 이동하는 그리디 알고리즘을 이용해봐야 할 듯하다.

- 시작시간 순으로 정렬하고, 시작시간이 같으면 종료시간 순으로 정렬
- 해당 회의 종료시간 <= 다음 회의 시작시간.

>>코드2. 시간초과

import sys

n = int(input())
meeting = []
for i in range(n):
    s, e = map(int, sys.stdin.readline().split())
    meeting.append([s, e])

meeting = sorted(meeting, key = lambda x: (x[0], x[1]))

ans = 0
for i in range(n):
    cnt = 0
    end = meeting[i][1]
    for j in range(i, n):
        if meeting[j][0] >= end:
            end = meeting[j][1]
            cnt += 1
    ans = max(ans ,cnt)
print(ans)

    
시간복잡도가 for문을 두번 돌려버리니 제곱이 되어 시간초과가 나왔다
그러나 시작시간을 기준으로 정렬을 해버리면, 
같은 시작시간이어도 종료시간에 따라 다른 더 긴 경로가 발생할 수 있으므로 전부 확인해야한다. 

그래서 생각을 해보니, 종료시간을 기준으로 우선 정렬하면, for문을 한번만 사용해도 된다.
종료시간 순으로 정렬을 한다면, 해당 회의 시작시간이 현재 회의 종료시간 이상이기만 하면,
가장 종료시간이 빠른 회의를 선택하면 된다. 
따라서 for 문을 한번만 이용하게 된다.

- 종료시간 순으로 정렬하고, 종료시간이 같으면 시작시간 순으로 정렬
- 해당 회의 종료시간 <= 다음 회의 시작시간

>> 정답코드

import sys

n = int(input())
meeting = []
for i in range(n):
    s, e = map(int, sys.stdin.readline().split())
    meeting.append([s, e])

meeting.sort(key = lambda x: (x[1], x[0]))

cnt, node = 0, 0
for start, end in meeting:
    if start >= node:
        node = end
        cnt += 1
print(cnt)

5. 문제 링크
https://www.acmicpc.net/problem/1931