[Programmers] P64063 호텔방 배정

[Programmers] P64063 호텔방 배정

Question

Language: Python

해당 문제는 전형적인 scheduling 유형의 문제이다. 주어진 시간/deadline에 대해서 처리를 할 수 없는데, 다음 deadline에 대해서 할당해주는 작업을 해줘야한다.

즉 1번 자리에 작업을 할당하고 나면 1번은 그 다음 시간인 2번과 연결시켜서, 1번으로의 작업이 요청되었을 때, 2번으로 자동 처리될 수 있도록 한다.

minimal_disjoint sets

def find_parent_compressed(parents,x):
    if parents[x]==0:
        return x
    if x!=parents[x]:
        parents[x]=find_parent_compressed(parents,parents[x])
    return parents[x]

def union_parents(parents,x,y):
    pre_x=find_parent_compressed(parents,x)
    pre_y=find_parent_compressed(parents,y)
    
    if pre_x < pre_y:
        parents[pre_x]=pre_y
    else:
        parents[pre_y]=pre_x

주의점

해당 문제 풀이 할때, 주의할 점이 있는데, 바로 K값이 매우 크기 때문에 단순히 parents 배열을 K 만큼 할당하게 되면, 메모리 초과 및 시간 초과가 발생할 수 있다.

따라서, dictionary를 통해 필요한 parents에 대해서만 이를 저장할 수 있도록 한다.

위 문제의 경우, 최대 20만개의 원소만 관리하면 된다.

Solution

from collections import defaultdict
import sys
def find_parent_compressed(parents,x):
    if parents[x]==0:
        return x
    if x!=parents[x]:
        parents[x]=find_parent_compressed(parents,parents[x])
    return parents[x]

def union_parents(parents,x,y):
    pre_x=find_parent_compressed(parents,x)
    pre_y=find_parent_compressed(parents,y)
    
    if pre_x < pre_y:
        parents[pre_x]=pre_y
    else:
        parents[pre_y]=pre_x

def solution(k, room_number):
    sys.setrecursionlimit(10**4)
    answer = []
    parents=defaultdict(int)

    for number in room_number:
        parent=find_parent_compressed(parents,number)
        answer.append(parent)
        union_parents(parents,parent,parent+1)
  
    return answer