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

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

Question

Language: Python

Difficulty: Platinum 5

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

이중 연결리스트 초기화

doubly linked list을 초기화 하는 부분으로, 노드를 생성하고 컨테이너에 노드들을 삽입한다.

def insert_into_container(heads,tails,nodes,container_counts,index,container):
    node=Node(index)
    #만약 컨테이너에 노드가 없는 경우
    if container_counts[container]==0:
        heads[container]=node     
    #그렇지 않은 경우, tail 뒤에 새로운 노드를 붙인다.
    else:
        tails[container].right=node
        node.left=tails[container]

    tails[container]=node
    container_counts[container]+=1
    nodes[index]=node

특정 컨테이너에 노드를 넣는 함수

출발지 컨테이너에서 노드를 빼내서 목적지 컨테이너에 노드를 추가하는 작업을 함수로 구현했다. 출발지 컨테이너가 비는 경우와 목적지가 빈 경우를 고려하여 상황에 맞게 처리한다. 노드 갯수에 상관없이 head, tail만 지정하면 head <-> tail 부분을 목적지 헤드로 이동시킨다.

#컨테이너에 노드 여러개를 삽입
def move_nodes_to_container(heads,tails,container_counts,src,dest,head,tail,moving_counts):
    dest_head=heads[dest]

    #목적지 컨테이너가 비어있는 경우
    if dest_head==None:
        tails[dest]=tail
    #그렇지 않은 경우 head의 앞에 연결
    else:
        dest_head.left=tail

    #이동 후 출발지 컨테이너에 남아있는 박스가 없는 경우
    if tail.right == None:
        tails[src]=None
    #그렇지 않은경우 head <-> tail 부분에서 tail의 연결을 끝는다.
    else:
        tail.right.left=None

    heads[src]=tail.right 
    tail.right=dest_head   
    heads[dest]=head

    container_counts[dest]+=moving_counts
    container_counts[src]-=moving_counts

헤드를 서로 교체하는 함수

두 개의 컨테이너에 대해 서로의 헤드를 교체하는 함수

def swith_heads(heads,tails,container_counts,src,dest):
    source_head=heads[src]
    dest_head=heads[dest]

    #목적지 헤드 뒤에 박스가 없는 경우 tails 값을 바꾼다.
    if dest_head.right==None:
        tails[dest]=source_head
    #그렇지 않은 경우, 목적지 헤드와 연결
    else:
        dest_head.right.left=source_head
        
    #출발지 헤드 뒤에 박스가 없으면 tails 바꾸기
    if source_head.right == None:
        tails[src]=dest_head
    #그렇지 않은 경우, 목적지 헤드와 연결
    else:
        source_head.right.left=dest_head

    #서로의 위치 이동        
    dest_head.right,source_head.right=source_head.right,dest_head.right

    heads[dest]=source_head
    heads[src]=dest_head

위의 함수들을 활용하면 문제의 조건에 따른 시뮬레이션을 구현하는 것이 가능하다.

Solution

class Node:
    def __init__(self,id):
        self.id=id
        self.left=None
        self.right=None
    
    def __str__(self):
        return "[Node: %d]" % (self.id)

#초기, 컨테이너에 박스를 추가하기 위한 함수    
def insert_into_container(heads,tails,nodes,container_counts,index,container):
    node=Node(index)
    #만약 컨테이너에 노드가 없는 경우
    if container_counts[container]==0:
        heads[container]=node     
    else:
        tails[container].right=node
        node.left=tails[container]

    tails[container]=node
    container_counts[container]+=1
    nodes[index]=node


#컨테이너에 노드 삽입
def move_nodes_to_container(heads,tails,container_counts,src,dest,head,tail,moving_counts):
    dest_head=heads[dest]

    #목적지 컨테이너가 비어있는 경우
    if dest_head==None:
        tails[dest]=tail
    #그렇지 않은 경우 head의 앞에 연결
    else:
        dest_head.left=tail

    #이동 후 출발지 컨테이너에 남아있는 박스가 없는 경우
    if tail.right == None:
        tails[src]=None
    #그렇지 않은경우 head <-> tail 부분에서 tail의 연결을 끝는다.
    else:
        tail.right.left=None

    heads[src]=tail.right 
    tail.right=dest_head   
    heads[dest]=head

    container_counts[dest]+=moving_counts
    container_counts[src]-=moving_counts

#서로의 헤드를 바꾸는 함수
def swith_heads(heads,tails,container_counts,src,dest):
    source_head=heads[src]
    dest_head=heads[dest]

    #목적지 헤드 뒤에 박스가 없는 경우 tails 값을 바꾼다.
    if dest_head.right==None:
        tails[dest]=source_head
    #그렇지 않은 경우, 목적지 헤드와 연결
    else:
        dest_head.right.left=source_head
        
    #출발지 헤드 뒤에 박스가 없으면 tails 바꾸기
    if source_head.right == None:
        tails[src]=dest_head
    #그렇지 않은 경우, 목적지 헤드와 연결
    else:
        source_head.right.left=dest_head

    #서로의 위치 이동        
    dest_head.right,source_head.right=source_head.right,dest_head.right

    heads[dest]=source_head
    heads[src]=dest_head


def solution():
    n_containers,n_nodes=queries[0][1],queries[0][2]
    init_nodes=queries[0][3:]
    container_counts=[0]*n_containers
    
    heads=[None] * n_containers
    tails=[None] * n_containers
    nodes=[None] * n_nodes
    
    #벨트 초기화 작업 진행
    for index in range(n_nodes):
        container=init_nodes[index]-1
        insert_into_container(heads,tails,nodes,container_counts,index,container)
    
    for index in range(1,n):
        command=queries[index][0]

        #물건 옮기기
        if command == 200:
            src,dest=map(lambda x: x-1,queries[index][1:])

            #출발지가 빈 경우에는 옮기지 않는다.
            if heads[src] == None:
                print(container_counts[dest])
                continue

            #출발지 헤드에 있는 모든 노드를 옮긴다.
            move_nodes_to_container(heads,tails,container_counts,src,dest,heads[src],tails[src],container_counts[src])            
            print(container_counts[dest])
        
        #앞 물건만 교체
        if command == 300:
            src,dest=map(lambda x: x-1,queries[index][1:])
            
            #두 개의 컨테이너가 모두 빈 경우에는 이동하지 않는다.
            if heads[src]==None and heads[dest]==None:
                print(container_counts[dest])
                continue
            
            #출발지가 빈 경우
            elif heads[src]==None:
                move_nodes_to_container(heads,tails,container_counts,dest,src,heads[dest],heads[dest],1)
            #목적지가 빈 경우
            elif heads[dest]==None:
                move_nodes_to_container(heads,tails,container_counts,src,dest,heads[src],heads[src],1)
            #둘다 차있는경우 서로의 헤드를 변경한다.
            else:
                swith_heads(heads,tails,container_counts,src,dest)

            print(container_counts[dest])      
            
        #물건 나누기
        if command == 400:
            src,dest=map(lambda x: x-1,queries[index][1:])

            #만약 src container에 박스 갯수가 1개 이하인 경우 이동하지 않는다.
            if container_counts[src] <=1:
                print(container_counts[dest])
                continue
                
            moving_counts=container_counts[src]//2
            head=heads[src]
            tail=heads[src]

            #n//2 위치를 파악하기 위해 tail 이동
            for _ in range(moving_counts-1):
                tail=tail.right

            move_nodes_to_container(heads,tails,container_counts,src,dest,head,tail,moving_counts)

            print(container_counts[dest])

        #선물 정보 출력
        if command == 500:
            item_id=queries[index][1]-1

            node=nodes[item_id]

            a,b=-1,-1

            a=node.left.id+1 if node.left != None else -1
            b=node.right.id+1 if node.right !=None else -1
            
            print(a+2*b)

        #벨트 정보 출력
        if command == 600:
            container_id=queries[index][1]-1

            c=container_counts[container_id]
            a=heads[container_id].id+1 if c!=0 else -1
            b=tails[container_id].id+1 if c!=0 else -1
            
            print(a+2*b+3*c)

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