글 읽기 - Python 0%에서 시간 초과로 오류가 납니다.

alsrl9 3년 전 0

기존 코드에서는 Robot을 리스트에 추가하고 Robot이 벨트에 올라가면 append, 내리면 del로 리스트를 조작했습니다.

제출했을 때 0%에서 시간 초과 판정을 받아 del 명령 후 리스트를 재정렬하는 과정에서 시간이 오래 걸리는 것으로 판단하여

Robot을 LinkedList로 구현했습니다.

요소를 삭제하는 시간을 줄이고 Robot을 새로 추가할 때도 tail 주소를 참조하여 시간을 단축시키려 했는데

정작 제출 결과는 0%에서 시간 초과 판정입니다.

제 코드의 어떤 점이 시간을 많이 잡아먹는 걸까요?

혹시 무한 루프를 타게 되는 부분이 있을까요?

코드의 문제점이나 속도를 개선할 방법을 알고 계신 분은 알려주시면 감사하겠습니다.

import sys

class block:
    def __init__(self, durability:int, isEmpty:bool):
        self.durability = durability
        self.isEmpty = isEmpty

class Robot:
    def __init__(self, num:int, next = None):
        self.num = num
        self.next = next

N, K = map(int, input().split()) # N <= 100
belt = [0]
robot_head = Robot(0)
robot_tail = robot_head
durability = list(map(int, input().split()))
for i in range(N + N):
    belt.append(block(durability[i], True))

leftTop = 1
rightTop = N

def get_pre(num:int):
    global N
    if num == 1:
        return 2 * N
    else:
        return num - 1

def get_next(num:int):
    global N
    if num == 2 * N:
        return 1
    else:
        return num + 1

def get_robot_off():
    global rightTop, belt, robot_head, robot_tail
    if belt[rightTop].isEmpty == True:
        return
    belt[rightTop].isEmpty = True
    temp = robot_head.next.next
    robot_head.next = temp
    if temp == None:
        robot_tail = robot_head

def belt_moves():
    global leftTop, rightTop, N
    leftTop = get_pre(leftTop)
    rightTop = get_pre(rightTop)
    get_robot_off()

def put_robot_on():
    global robot_head, robot_tail, leftTop, belt
    if belt[leftTop].isEmpty == False or belt[leftTop].durability == 0:
        return
    belt[leftTop].isEmpty = False
    belt[leftTop].durability -= 1

    temp = Robot(leftTop)
    robot_tail.next = temp
    robot_tail = temp

def robots_move():
    global robot_head, belt
    temp = robot_head.next
    while temp != None:
        if belt[get_next(temp.num)].durability == 0 or belt[get_next(temp.num)].isEmpty == False:
            temp = temp.next
            continue
        belt[temp.num].isEmpty = True
        temp.num = get_next(temp.num)
        belt[temp.num].durability -= 1
        belt[temp.num].isEmpty = False
        temp = temp.next
        get_robot_off()
            
round = 1
while(True):
    belt_moves()
    robots_move()
    put_robot_on()

    #check durability of all blocks
    cnt = 0
    for i in range(1, 2 * N + 1):
        if belt[i].durability == 0:
            cnt += 1
    if cnt >= K:
        break
    round += 1

print(round)

alsrl9 3년 전 1

pypy3으로 제출했을 때는 통과가 되네요. ㅠㅠ

의문이 계속 늘어만 갑니다.

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

문제

문제

출처

ICPC

Python 0%에서 시간 초과로 오류가 납니다.

alsrl9 3년 전 0

alsrl9 3년 전 1

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말