글 읽기 - 시간 복잡도에 관한 질문

djm04092 2년 전 0

해당 코드에서 삽입할때 이진탐색을 이용하여 list의 적절한 위치에 삽입해주는 방식을 이용하였는데 이렇게하면 시간복잡도가 logk 가 되는 것이 아닌가요?

어떤 부분 때문에 시간초과가 나는 것인지 잘 모르겠어서 질문 올립니다.

class DoublePriorityQueue:
    def __init__(self):
        self.arr = []

    def __len__(self):
        return len(self.arr)

    def append(self, data):

        if len(self.arr) == 0:
            self.arr.append(data)
        else:
            start, end = 0, len(self.arr) - 1
            while start <= end:
                mid = (start + end) // 2
                if self.arr[mid] >= data:
                    end = mid - 1
                else:
                    start = mid + 1
            self.arr = self.arr[:end+1] + [data] + self.arr[start:]

    def popleft(self):
        self.arr = self.arr[1:]

    def pop(self):
        self.arr = self.arr[:-1]


T = int(input())
for _ in range(T):
    k = int(input())
    dq = DoublePriorityQueue()
    for __ in range(k):
        op, num_str = input().split()
        if op == "I":
            dq.append(int(num_str))
        elif op == "D":
            if num_str == "1":
                dq.pop()
            elif num_str == "-1":
                dq.popleft()
    if len(dq) == 0:
        print("EMPTY")
    else:
        print(dq.arr[-1], dq.arr[0])

댓글을 작성하려면 로그인해야 합니다.

문제

문제

출처

ICPC

시간 복잡도에 관한 질문

djm04092 2년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말