###前提・実現したいこと
AOJの
Dubly Linked List(http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=ALDS1_3_C&lang=jp)
をPython3で解いているのですが
どうしても実行時間が規定を超えてしまいます。
下記のコードでどこか計算量を削れるところはあるでしょうか。
よろしくお願いします。
###該当のソースコード
Python
1#http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=ALDS1_3_C&lang=jp 2#双方向連結リスト 3 4NEXT = 2 5DATA = 1 6PREV = 0 7def dll_processor(operations): 8 9 front = None 10 end = None 11 12 for o in operations: 13 if o[0] == "insert": 14 front, end = insert(front, end, o[1]) 15 elif o[0] == "delete": 16 front, end = delete(front, end, o[1]) 17 elif o[0] == "deleteFirst": 18 front, end = delete_first(front, end) 19 elif o[0] == "deleteLast": 20 front, end = delete_last(front, end) 21 #print(get_list(front)) 22 23 return get_list(front) 24 25def get_list(front): 26 if not front: 27 return [] 28 29 l = [] 30 target = front 31 while True: 32 l.append(target[DATA]) 33 if not target[NEXT]: 34 break 35 target = target[NEXT] 36 return l 37 38def insert(front, end, target): 39 node = [None, target, None] 40 if front: 41 front[PREV] = node 42 node[NEXT] = front 43 return node, end 44 else: 45 return node, node 46 47def delete(front, end,target): 48 49 delete_node = front 50 while not delete_node[DATA] == target: 51 delete_node = delete_node[NEXT] 52 if delete_node == None: 53 return front, end 54 55 if delete_node[PREV] == None: 56 delete_node[NEXT][PREV] = None 57 return delete_node[NEXT], end 58 elif delete_node[NEXT] == None: 59 delete_node[PREV][NEXT] = None 60 return front, delete_node[PREV] 61 else: 62 delete_node[NEXT][PREV] = delete_node[PREV] 63 delete_node[PREV][NEXT] = delete_node[NEXT] 64 return front, end 65 66def delete_last(front, end): 67 68 if not end[PREV]: 69 return None, None 70 else: 71 end[PREV][NEXT] = None 72 return front, end[PREV] 73 74def delete_first(front, end): 75 76 if not front[NEXT]: 77 return None, None 78 else: 79 front[NEXT][PREV] = None 80 return front[NEXT], end 81 82def main(): 83 n_list = int(input()) 84 target_list = [input().split() for i in range(n_list)] 85 print(*dll_processor(target_list)) 86 87if __name__ == "__main__": 88 main()
バッドをするには、ログインかつ
こちらの条件を満たす必要があります。