글 읽기 - [Python] 런타임 오류 + 시간 초과 부탁드립니다

kjyul1112 3년 전 0

테스트 케이스는 모두 통과하는데 제출하니 런타임 오류가 뜨네요 ㅠㅠ

sys.setrecursionlimit을 높여줬더니 시간 초과가 뜹니다 ㅠㅠ

0으로 나누는 케이스에 대해서도 처리하고 인덱스도 다시 살펴 봤는데 왜 런타임이 자꾸 뜨는지 잘 모르겠네요 ㅠㅠ

도와주시면 정말 감사하겠습니다.

from collections import deque
import copy
# import sys
# sys.setrecursionlimit(10000)



N, M, T = list(map(int, input().split()))

circle_que = []
for i in range(N):
    circle_que.append([])
    data = list(map(int, input().split()))
    circle_que[i] = deque(data)


di = [1, 0, -1, 0]
dj = [0, 1, 0, -1]

erase_chk = False
task_que = deque()


def erase_duplicate(start_i, start_j, compare_val, _c_que):

    global erase_chk
    global task_que


    c_que = copy.deepcopy(_c_que)

    new_compare_chk = False
    if(compare_val == -1):#컴페어를 이제 시작해야한다.
        new_compare_chk = True#new_i, new_j의 값과 같은 경우 start도 지워줘야 함
        compare_val = c_que[start_i][start_j]
    for k in range(4):
        new_i = start_i + di[k]
        new_j = start_j + dj[k]


        if((new_j == -1 and start_j == 0)):#끝과 끝을 비교하는 경우(원판의 특성 -> j만 적용)
            new_j = M - 1

        if(start_j == M - 1 and new_j == M):
            new_j = 0

        dup_chk = False

        for i in range(len(task_que)):
            #이미 비교를 한 상태임
            if(task_que[i][0] == new_i and task_que[i][1] == new_j and task_que[i][2] == start_i and task_que[i][3] == start_j):
                dup_chk = True

        if(dup_chk):
            continue

        task_que.append([new_i, new_j, start_i, start_j])

        if(new_i < 0 or new_j < 0 or new_i >= N or new_j >= M or c_que[new_i][new_j] == -1):#index out of range or already erased
            continue

        if(c_que[new_i][new_j] == compare_val):#지워줘야 하는 경우
            
            if(new_compare_chk):#새로운 지우기 시작!
                c_que[start_i][start_j] = -1

            c_que[new_i][new_j] = -1
            

            if(not erase_chk):#지우기 작업 자체가 실행 되었는지 아닌지 판단
                erase_chk = True

            c_que = erase_duplicate(new_i, new_j, compare_val, c_que)
        
        else:#지우진 못했지만 새로운 것을 찾아 탐색
            c_que = erase_duplicate(new_i, new_j, -1, c_que)

    return c_que


def average_arrange(_c_que):

    global avg_chk

    c_que = copy.deepcopy(_c_que)
    count = 0
    sum_val = 0

    #평균 구하기
    for i in range(N):
        for j in range(M):
            if(c_que[i][j] > 0):
                sum_val += c_que[i][j]
                count += 1
    if(count != 0):
        avg_val = sum_val / count

        #값 재설정
        for i in range(N):
            for j in range(M):
                if(c_que[i][j] != -1):
                    if(float(c_que[i][j]) > avg_val):
                        c_que[i][j] -= 1
                    elif(float(c_que[i][j]) < avg_val):
                        c_que[i][j] += 1
    else:
        avg_chk = False

    return c_que


for _ in range(T):
    x, d, k = list(map(int, input().split()))

    if(d == 0):#시계 방향이라면
        k = M - k#반시계방향 방식으로 전환

    

    #회전 시키기 작업    
    cnt = 0
    while True:
        selected_idx = (cnt + 1) * x - 1
        cnt += 1

        if(selected_idx >= N):#index 벗어남
            break
        
        if(max(circle_que[selected_idx]) == -1):#이미 해당 원판은 모두 다 지워졌다.
            continue
        
        #회전 시켜주기
        for _ in range(k):#k번 돌리기 작업 수행
            tmp_val = circle_que[selected_idx].popleft()
            circle_que[selected_idx].append(tmp_val)

        

    #erase 작업이 진행되었는지 확인
    erase_chk = False

    #지우기 작업
    circle_que = erase_duplicate(0, 0, -1, circle_que)
    task_que.clear()#중복 작업 방지 위해 사용했던 큐를 지워준다.

    #circle_que가 전부 다 -1인경우 False 반환
    avg_chk = True
    if(not erase_chk):#erase가 한번도 진행되지 않았다면
        circle_que = average_arrange(circle_que)
        if(not avg_chk):
            break

        
result_val = 0

for i in range(N):
    for j in range(M):
        if(circle_que[i][j] > 0):
            result_val += circle_que[i][j]

print(result_val)

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

문제

문제

출처

ICPC

[Python] 런타임 오류 + 시간 초과 부탁드립니다

kjyul1112 3년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말