[Samsung] 2022-2 오전 2번 산타의 선물공장

[Samsung] 2022-2 오전 2번 산타의 선물공장

Question

Language: Python

Difficulty: Platinum 4

해당 문제는 doubly linked list을 직접적으로 구현해서 문제를 풀이해야 시간 복잡도 내 풀이가 가능하다. 각 노드에 대한 컨테이너 인덱스를 저장해서 특정 노드의 위치를 파악할 때 시간 효율성을 높이도록 한다.

공장 설립

doubly linked list을 초기화 하는 부분으로 노드를 생성하고, 각 노드들의 양끝을 서로 연결한다.

n,m=queries[0][1],queries[0][2]
box_indexes=queries[0][3:n+3]
weights=queries[0][n+3:]
conveyor_indexes=[i for i in range(m)]

#box index에 대한 무게 매핑
node_maps={}
unit=n//m
heads=[]
tails=[]

#노드 생성
for conveyor_index in range(m):
    start,end=unit*conveyor_index,unit*conveyor_index+unit
    for i in range(start,end):
        node_maps[box_indexes[i]]=[conveyor_index,Node(box_indexes[i],weights[i])]

#노드 연결
for conveyor_index in range(m):
    start,end=unit*conveyor_index,unit*conveyor_index+unit
    heads.append(node_maps[box_indexes[start]][1])
    for i in range(start+1,end-1):
        node_maps[box_indexes[i]][1].connect(node_maps[box_indexes[i-1]][1],node_maps[box_indexes[i+1]][1])
    tails.append(node_maps[box_indexes[end-1]][1])

물건 하차

각 컨테이너 별로 헤드의 무게를 확인해서, 주어진 무게 기준보다 낮은 헤드들은 빼내고, 그렇지 않은 경우 헤드를 뒤로 옮긴다.

컨테이너가 고장이거나, 빈 컨테이너 인 경우 탐색을 하지 않는다. 만약, 무게 기준에 부합하지 않지만 노드가 1개만 존재하는 경우 뒤로 옮기는 작업을 생략한다.

weight_sum=0
for conveyor_index in range(m):
    #컨베이어 벨트가 고장인 경우
    if conveyor_index != find_parent_compressed(conveyor_indexes,conveyor_index):
        continue
    head=heads[conveyor_index]
    tail=tails[conveyor_index]
    #빈 노드인 경우
    if head == None:
        continue
    #주어진 무게 기준 보다 낮은 경우 해당 list에서 값을 빼낸다.
    if head.weight <= option:
        weight_sum+=head.weight
        #헤드 제거
        if head.right != None:
            head.right.left=None
        del node_maps[head.id]
        heads[conveyor_index]=head.right
    #맨 앞의 박스를 맨 뒤로 옮긴다. 이때, 박스가 1개 뿐인 경우 작업 수행 X
    elif head!=tail:
        tail.right=head
        head.left=tail
        tails[conveyor_index]=head
    
        head.right.left=None
        heads[conveyor_index]=head.right
        head.right=None

물건 제거

특정 물건을 제거하고자 하는 경우, 해당 노드의 컨테이너 인덱스를 찾은 다음, 노드의 left, right을 서로 연결해주므로써 노드의 연결을 끊고 노드를 삭제한다.

이때 해당 노드가 head, tail 인 경우 head, tail을 새로 지정하는 작업을 수행한다.

#물건 제거
elif command==300:
    #해당 박스가 없으면 -1 출력
    if option not in node_maps.keys():
        print(-1)
        continue
    conveyor_index,node=node_maps[option]
    conveyor_index=find_parent_compressed(conveyor_indexes,conveyor_index)

    if node.left != None:
        node.left.right=node.right
    if node.right !=None:
        node.right.left=node.left
    
    #헤드 인경우
    if node.left ==None:
        heads[conveyor_index]=node.right
    #테일인 경우
    if node.right==None:
        tails[conveyor_index]=node.left

        
    print(option)
    del node_maps[option]

물건 찾기

특정 노드의 위치를 찾는 작업 에서는, 노드가 있는 경우 해당 노드를 기준으로 위에 있는 노드를 포함해서 모두 앞으로 당기는 작업을 수행해야한다.

만일 노드가 헤드인 경우에는 위의 작업을 수행할 필요가 없다.

#해당 박스가 없으면 -1 출력
if option not in node_maps.keys():
    print(-1)
    continue
conveyor_index,node=node_maps[option]
conveyor_index=find_parent_compressed(conveyor_indexes,conveyor_index)

#이미 헤드인 경우 작업 생략
if node != heads[conveyor_index]:
    heads[conveyor_index].left=tails[conveyor_index]
    tails[conveyor_index].right=heads[conveyor_index]

    node.left.right=None
    tails[conveyor_index]=node.left

    node.left=None
    heads[conveyor_index]=node

컨테이너 고장

컨테이너가 고장인 경우 인접한 컨테이너로 노드들을 옮기는 작업을 수행해야한다. 이때 기존 컨테이너에 있던 노드들의 컨테이너 인덱스를 변경해줘야하는데, 이를 일일히 수행하게 되면 시간 효율성이 따라진다. 따라서 컨테이어 인덱스에 대한 매핑을 저장해서 기존 컨테이너 인덱스를 새로운 컨테이너 인덱스로 연결해준다.이를 위해 multiple-disjoint set을 활용해서 연결한다.

def find_parent_compressed(parents,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)
    parents[pre_x]=pre_y

current_converyor_index=option-1
#이미 고장 인경우
if current_converyor_index != find_parent_compressed(conveyor_indexes,current_converyor_index):
    print(-1)
    continue
moved_conveyor_index=0
#정상적인 컨테이너를 찾을 때까지 탐색 수행
for i in range(1,m):
    moved_conveyor_index=(current_converyor_index + i)%m
    #탐색한 다음 컨베이어가 고장인 경우 넘어간다.
    if moved_conveyor_index == find_parent_compressed(conveyor_indexes,moved_conveyor_index):
        break
    
#해당 컨테이너에 있던 노드의 컨테이너 인덱스를 변경한다.
union_parents(conveyor_indexes,current_converyor_index,moved_conveyor_index)

tails[moved_conveyor_index].right=heads[current_converyor_index]
heads[current_converyor_index].left=tails[moved_conveyor_index]
tails[moved_conveyor_index]=tails[current_converyor_index]

heads[current_converyor_index]=None
tails[current_converyor_index]=None

Solution

from collections import deque
from math import inf
from os.path import dirname,join
class Node:
    def __init__(self,id,weight):
        self.id=id
        self.weight=weight
        self.left=None
        self.right=None
    
    def __str__(self):
        return "[id: %d, weight: %d]" % (self.id,self.weight)

    def connect(self,left,right):
        self.left=left
        left.right=self
        self.right=right
        right.left=self
    
def find_parent_compressed(parents,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)
    parents[pre_x]=pre_y


def solution():
    n,m=queries[0][1],queries[0][2]
    box_indexes=queries[0][3:n+3]
    weights=queries[0][n+3:]
    conveyor_indexes=[i for i in range(m)]

    #box index에 대한 무게 매핑
    node_maps={}
    unit=n//m
    heads=[]
    tails=[]

    #노드 생성
    for conveyor_index in range(m):
        start,end=unit*conveyor_index,unit*conveyor_index+unit
        for i in range(start,end):
            node_maps[box_indexes[i]]=[conveyor_index,Node(box_indexes[i],weights[i])]

    #노드 연결
    for conveyor_index in range(m):
        start,end=unit*conveyor_index,unit*conveyor_index+unit
        heads.append(node_maps[box_indexes[start]][1])
        for i in range(start+1,end-1):
            node_maps[box_indexes[i]][1].connect(node_maps[box_indexes[i-1]][1],node_maps[box_indexes[i+1]][1])
        tails.append(node_maps[box_indexes[end-1]][1])
    
    for command, option in queries[1:]:
        #물건 하차
        if command == 200:
            weight_sum=0
            for conveyor_index in range(m):
                #컨베이어 벨트가 고장인 경우
                if conveyor_index != find_parent_compressed(conveyor_indexes,conveyor_index):
                    continue
                head=heads[conveyor_index]
                tail=tails[conveyor_index]
                #빈 노드인 경우
                if head == None:
                    continue
                #주어진 무게 기준 보다 낮은 경우 해당 list에서 값을 빼낸다.
                if head.weight <= option:
                    weight_sum+=head.weight
                    #헤드 제거
                    if head.right != None:
                        head.right.left=None
                    del node_maps[head.id]
                    heads[conveyor_index]=head.right
                #맨 앞의 박스를 맨 뒤로 옮긴다. 이때, 박스가 1개 뿐인 경우 작업 수행 X
                elif head!=tail:
                    tail.right=head
                    head.left=tail
                    tails[conveyor_index]=head
                
                    head.right.left=None
                    heads[conveyor_index]=head.right
                    head.right=None
                    
            print(weight_sum)
        #물건 제거
        elif command==300:
            #해당 박스가 없으면 -1 출력
            if option not in node_maps.keys():
                print(-1)
                continue
            conveyor_index,node=node_maps[option]
            conveyor_index=find_parent_compressed(conveyor_indexes,conveyor_index)

            if node.left != None:
                node.left.right=node.right
            if node.right !=None:
                node.right.left=node.left
            
            #헤드 인경우
            if node.left ==None:
                heads[conveyor_index]=node.right
            #테일인 경우
            if node.right==None:
                tails[conveyor_index]=node.left

                
            print(option)
            del node_maps[option]
        #물건 확인
        elif command == 400:
            #해당 박스가 없으면 -1 출력
            if option not in node_maps.keys():
                print(-1)
                continue
            conveyor_index,node=node_maps[option]
            conveyor_index=find_parent_compressed(conveyor_indexes,conveyor_index)
            
            #이미 헤드인 경우 작업 생략
            if node != heads[conveyor_index]:
                heads[conveyor_index].left=tails[conveyor_index]
                tails[conveyor_index].right=heads[conveyor_index]

                node.left.right=None
                tails[conveyor_index]=node.left

                node.left=None
                heads[conveyor_index]=node

            print(conveyor_index+1)
        #벨트 고장
        else:
            current_converyor_index=option-1
            #이미 고장 인경우
            if current_converyor_index != find_parent_compressed(conveyor_indexes,current_converyor_index):
                print(-1)
                continue
            moved_conveyor_index=0
            #정상적인 컨테이너를 찾을 때까지 탐색 수행
            for i in range(1,m):
                moved_conveyor_index=(current_converyor_index + i)%m
                #탐색한 다음 컨베이어가 고장인 경우 넘어간다.
                if moved_conveyor_index == find_parent_compressed(conveyor_indexes,moved_conveyor_index):
                    break
               
            #해당 컨테이너에 있던 노드의 컨테이너 인덱스를 변경한다.
            union_parents(conveyor_indexes,current_converyor_index,moved_conveyor_index)

            tails[moved_conveyor_index].right=heads[current_converyor_index]
            heads[current_converyor_index].left=tails[moved_conveyor_index]
            tails[moved_conveyor_index]=tails[current_converyor_index]

            heads[current_converyor_index]=None
            tails[current_converyor_index]=None
            
            print(current_converyor_index+1)



if __name__ == "__main__":
    q=int(input())
    queries=[list(map(int,input().split())) for _ in range(q)]
    solution()

Failed Solution

아래는 deque를 활용하여 작성해본 코드이다.

from collections import deque,defaultdict
from math import inf
    
def find_parent_compressed(parents,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)
    parents[pre_x]=pre_y


def solution():
    n,m=queries[0][1],queries[0][2]
    box_indexes=queries[0][3:n+3]
    weights=queries[0][n+3:]
    conveyor_indexes=[i for i in range(m)]

    #box index에 대한 무게 매핑
    node_maps={}
    unit=n//m
    heads=[]
    tails=[]

    conveyors=[deque() for _ in range(m)]

    #deque 생성
    for conveyor_index in range(m):
        start,end=unit*conveyor_index,unit*conveyor_index+unit
        for i in range(start,end):
            node_maps[box_indexes[i]]=(conveyor_index,weights[i])
            conveyors[conveyor_index].append((box_indexes[i],weights[i]))

    
    for command, option in queries[1:]:
        #물건 하차
        if command == 200:
            weight_sum=0
            for conveyor_index in range(m):
                #컨베이어 벨트가 고장인 경우
                if conveyor_index != find_parent_compressed(conveyor_indexes,conveyor_index):
                    continue
                
                conveyor=conveyors[conveyor_index] 
                if len(conveyor) == 0:
                    continue

                #주어진 무게 기준 보다 낮은 경우 해당 list에서 값을 빼낸다.
                if conveyor[0][1] <= option:
                    weight_sum+=conveyor[0][1]

                    del node_maps[conveyor[0][0]]
                    conveyors[conveyor_index].popleft()

                #맨 앞의 박스를 맨 뒤로 옮긴다. 이때, 박스가 1개 뿐인 경우 작업 수행 X
                elif len(conveyor) > 1:
                    conveyors[conveyor_index].append(conveyors[conveyor_index].popleft())
                    
            print(weight_sum)
        #물건 제거
        elif command==300:
            #해당 박스가 없으면 -1 출력
            if option not in node_maps.keys():
                print(-1)
                continue
            conveyor_index,weight=node_maps[option]
            conveyor_index=find_parent_compressed(conveyor_indexes,conveyor_index)

            conveyors[conveyor_index].remove((option,weight))

            print(option)
            del node_maps[option]
        #물건 확인
        elif command == 400:
            #해당 박스가 없으면 -1 출력
            if option not in node_maps.keys():
                print(-1)
                continue
            conveyor_index,weight=node_maps[option]
            conveyor_index=find_parent_compressed(conveyor_indexes,conveyor_index)
            node_index=conveyors[conveyor_index].index((option,weight))
            
            temp=deque()
            length=len(conveyors[conveyor_index])
            for index in range(node_index,length):
                temp.append(conveyors[conveyor_index].pop())

            for index in range(node_index,length):
                conveyors[conveyor_index].appendleft(temp.popleft())
            print(conveyor_index+1)
        #벨트 고장
        else:
            current_converyor_index=option-1
            #이미 고장 인경우
            if current_converyor_index != find_parent_compressed(conveyor_indexes,current_converyor_index):
                print(-1)
                continue
            moved_conveyor_index=0
            #정상적인 컨테이너를 찾을 때까지 탐색 수행
            for i in range(1,m):
                moved_conveyor_index=(current_converyor_index + i)%m
                #탐색한 다음 컨베이어가 고장인 경우 넘어간다.
                if moved_conveyor_index == find_parent_compressed(conveyor_indexes,moved_conveyor_index):
                    break
               
            #해당 컨테이너에 있던 노드의 컨테이너 인덱스를 변경한다.
            union_parents(conveyor_indexes,current_converyor_index,moved_conveyor_index)
            temp=deque()
            length=len(conveyors[current_converyor_index])
            for index in range(length):
                temp.append(conveyors[current_converyor_index].pop())
            for index in range(length):
                conveyors[moved_conveyor_index].append(temp.pop())
            print(current_converyor_index+1)



if __name__ == "__main__":
    q=int(input())
    queries=[list(map(int,input().split())) for _ in range(q)]
    solution()