산타의 선물 공장2

더블링크드리스트 자료구조를 구현해야하는 문제.

 

당연히 알고있지만, 도저히 구현할 방법이 떠오르지 않아서

막 구현했다가 얄짤없이 시간초과에서 막혔다.

for문으로 딕셔너리를 전부 조회하면서(O(n)) element in (O(n))으로 찾고, 찾으면 index를 한번 더 찾기 때문에 (O(n)) 

최악의 경우 O(n^3) 이 되버려서 말도 안되는 풀이라고 생각은 했다...

최대 명령의 개수 10**5  최대 벨트의 개수10**5 최대 선물의 개수 10**5..

 

갓갓갓 호석님의 풀이를 다시 코드 짜봐야겠음...

import sys
from collections import defaultdict
from collections import deque
q = int(sys.stdin.readline().strip())
belt_dict = defaultdict(deque)

def foundation_factory(belt_count, item_count, items):
    global belt_dict
    belt_dict = {i+1:deque([]) for i in range(belt_count)}

    for idx in range(len(items)):
        belt_num = items[idx]
        item_num = idx + 1
        belt_dict[belt_num].append(item_num)
    return

def move_all_item(start, end):
    global belt_dict
    belt_dict[end].extendleft(list(reversed(belt_dict[start])))
    belt_dict[start] = deque([])
    print(len(belt_dict[end]))
    return

def tran_first_item(start, end):
    global belt_dict
    if len(belt_dict[start]) != 0 and len(belt_dict[end]) != 0:
        belt_dict[start][0], belt_dict[end][0] =  belt_dict[end][0], belt_dict[start][0]
    elif len(belt_dict[start]) == 0 and len(belt_dict[end]) != 0:
        belt_dict[start].append(belt_dict[end].popleft())
    elif len(belt_dict[start]) != 0 and len(belt_dict[end]) == 0:
        belt_dict[end].append(belt_dict[start].popleft())
    print(len(belt_dict[end]))
    return

def devide_items(start, end):
    global belt_dict
    move_item_count = len(belt_dict[start]) // 2
    move_items = list(belt_dict[start])[:move_item_count]
    belt_dict[end].extendleft(list(reversed(move_items)))
    belt_dict[start] = deque(list(belt_dict[start])[move_item_count:])
    print(len(belt_dict[end]))
    return

def get_item_info(item_num):
    global belt_dict
    a = -1
    b = -1
    for belt_num in belt_dict:
        if item_num in belt_dict[belt_num]:
            idx = belt_dict[belt_num].index(item_num)
            if 0 != idx:
                a = belt_dict[belt_num][idx - 1]
            if len(belt_dict[belt_num]) > idx + 1:
                b = belt_dict[belt_num][idx + 1]
            break
    print(a + 2 * b)
    return

def get_belt_info(belt_num):
    global belt_dict
    c = len(belt_dict[belt_num])
    a = -1
    b = -1
    if len(belt_dict[belt_num]) != 0:
        a = belt_dict[belt_num][0]
        b = belt_dict[belt_num][-1]
    print(a + 2*b + 3*c)
    return

for _ in range(q):
    command = list(map(int, sys.stdin.readline().strip().split()))
    if command[0] == 100:
        foundation_factory(command[1], command[2], command[3:])
    elif command[0] == 200:
        move_all_item(command[1], command[2])
    elif command[0] == 300:
        tran_first_item(command[1], command[2])
    elif command[0] == 400:
        devide_items(command[1], command[2])
    elif command[0] == 500:
        get_item_info(command[1])
    elif command[0] == 600:
        get_belt_info(command[1])

 

 

나름 다시 짠 코드...dictionary 로 더블링크드리스트 구현을 했는데...

50퍼에서 시간초과가남...문제였던 O(n^3) 을 없앴는데.. 어디서 문제이지....

 

import sys
from collections import defaultdict
from collections import deque
q = int(sys.stdin.readline())
belt_dict = defaultdict(deque)
item_dict = defaultdict(dict)
def foundation_factory(belt_count, item_count, items):
    global belt_dict, item_dict
    belt_dict = {i+1:deque([]) for i in range(belt_count)}

    for idx in range(len(items)):
        belt_num = items[idx]
        item_num = idx + 1
        item_dict[item_num]["next"] = -1
        item_dict[item_num]["prev"] = -1
        if len(belt_dict[belt_num]) != 0:
            prev_item = belt_dict[belt_num][-1]
            item_dict[prev_item]["next"] = item_num
            item_dict[item_num]["prev"] = prev_item 
        belt_dict[belt_num].append(item_num)
    return

def move_all_item(start, end):
    global belt_dict, item_dict
    if len(belt_dict[start]) != 0 and len(belt_dict[end]) != 0:
        first_num = belt_dict[end][0]
        last_num = belt_dict[start][-1]
        item_dict[last_num]["next"] = first_num
        item_dict[first_num]["prev"] = last_num


    belt_dict[end].extendleft(list(reversed(belt_dict[start])))
    belt_dict[start] = deque([])

    print(len(belt_dict[end]))
    return

def tran_first_item(start, end):
    global belt_dict, item_dict
    if len(belt_dict[start]) != 0 and len(belt_dict[end]) != 0:
        belt_dict[start][0], belt_dict[end][0] =  belt_dict[end][0], belt_dict[start][0]
        item_dict[belt_dict[start][0]]["next"], item_dict[belt_dict[end][0]]["next"] = item_dict[belt_dict[end][0]]["next"], item_dict[belt_dict[start][0]]["next"]
        if len(belt_dict[start]) >= 2:
            item_dict[belt_dict[start][1]]["prev"] = belt_dict[start][0]
        if len(belt_dict[end]) >= 2:
            item_dict[belt_dict[end][1]]["prev"] = belt_dict[end][0]
    elif len(belt_dict[start]) == 0 and len(belt_dict[end]) != 0:
        belt_dict[start].append(belt_dict[end].popleft())
        if len(belt_dict[end]) != 0:
            item_dict[belt_dict[end][0]]["prev"] = -1
        item_dict[belt_dict[start][0]]["prev"] = -1
        item_dict[belt_dict[start][0]]["next"] = -1
        # item_

    elif len(belt_dict[start]) != 0 and len(belt_dict[end]) == 0:
        belt_dict[end].append(belt_dict[start].popleft())
        if len(belt_dict[start]) != 0:
            item_dict[belt_dict[start][0]]["prev"] = -1
        item_dict[belt_dict[end][0]]["prev"] = -1
        item_dict[belt_dict[end][0]]["next"] = -1

    print(len(belt_dict[end]))
    return

def devide_items(start, end):
    global belt_dict, item_dict
    move_item_count = len(belt_dict[start]) // 2
    move_items = list(belt_dict[start])[:move_item_count]

    if len(move_items) != 0:

        item_dict[move_items[0]]["prev"] = -1 #move앞처리

        if len(belt_dict[end]) != 0:
            item_dict[belt_dict[end][0]]["prev"] = move_items[-1] #end 앞처리
            item_dict[move_items[-1]]["next"] = belt_dict[end][0] #move뒷처리
        else:
            item_dict[move_items[-1]]["next"] = -1 #move 뒷처리

        belt_dict[start]

    belt_dict[end].extendleft(list(reversed(move_items)))
    belt_dict[start] = deque(list(belt_dict[start])[move_item_count:])

    if len(belt_dict[start]) != 0:
        item_dict[belt_dict[start][0]]["prev"] = -1 #start 앞처리

    print(len(belt_dict[end]))
    return

def get_item_info(item_num):
    global belt_dict, item_dict
    a = item_dict[item_num]["prev"]
    b = item_dict[item_num]["next"]
    print(a + 2 * b)
    return

def get_belt_info(belt_num):
    global belt_dict
    c = len(belt_dict[belt_num])
    a = -1
    b = -1
    if len(belt_dict[belt_num]) != 0:
        a = belt_dict[belt_num][0]
        b = belt_dict[belt_num][-1]
    print(a + 2*b + 3*c)
    return

for _ in range(q):
    command = list(map(int, sys.stdin.readline().strip().split()))
    if command[0] == 100:
        foundation_factory(command[1], command[2], command[3:])
    elif command[0] == 200:
        move_all_item(command[1], command[2])
    elif command[0] == 300:
        tran_first_item(command[1], command[2])
    elif command[0] == 400:
        devide_items(command[1], command[2])
    elif command[0] == 500:
        get_item_info(command[1])
    elif command[0] == 600:
        get_belt_info(command[1])

 

역시 갓갓갓 호석님...

모든 아이템을 옮길 경우에 extendleft 메서드 사용시 시간 복잡도가 O(덱길이) 이다.

따라서 최악의 경우에 10^5 * 10^5 연산이 되버려서 deque로 섞어 구현시 풀리지 않음... 하앙

그냥 무조건 더블링크드리스트를 구현해야함.