글 읽기 - [파이썬]pypy 시간 초과나는 이유를 잘 모르겠습니다.

wksehfdl8 3년 전 1

처음에 heapq를 사용해봤다가, deque 을 이용해 구현해보았는데, 결국 시간초과가 납니다.

deque 을 사용해 pop 이나 append 는 전부 O(1)일테고, 유일하게 오래 걸릴만한 부분은 46 줄에 copy줄때뿐입니다..

카피한번정도때문에 시간초과가 날까 싶은데, 다른 시간초과 날만한 부분이 보이시면

알려주시면 정말 감사하겠습니다!!

추가: 77번줄의 코드로 pypy 통과하였습니다....

첫번째 코드의 경우 전체를 (x,y,age) deque로 두었고

두번째 코드의 경우 dictionary를 통해 trees[x][y] 당 deque 을 하나씩 두엇는데

오히려 첫번째 코드가 조금더 빠르다 생각했는데.. 아닌가요.?

세세한 부분이 헷갈리네요 ㅠㅠ 도움주시면 감사하겠습니다!!

import sys
from collections import deque

input = sys.stdin.readline

N,M,K = map(int,input().split())
A = [list(map(int,input().split())) for _ in range(N)]
trees=[]
for _ in range(M):
    x,y,age = map(int,input().split())
    trees.append((age,x-1,y-1))

dy=[-1,-1,-1,0,0,1,1,1]
dx=[-1,0,1,-1,1,-1,0,1]
# 0 1 2
# 3   4
# 5 6 7
trees.sort()
trees=deque(trees)
ingredient = [[5]*N for _ in range(N)]  # 양분

# 봄 = 나이만큼 양분 섭취 후 나이++, 나이가 어린 나무부터 양분섭취, 부족할시 즉사
# 여름 = 봄에 죽은 나무나이/2 가 양분으로 추가
# 가을 = 번식, 나무나이가 5의 배수일시 인접한칸에 나무생성
# 겨울 = 양분추가

def spring():
    dead=[]
    global trees

    for _ in range(len(trees)):
        age,x,y = trees.popleft()
        if ingredient[x][y] < age:
            dead.append((age,x,y))
        else:
            ingredient[x][y] -=age
            trees.append((age+1,x,y))
    return dead

def summer(dead):
    for age,x,y in dead:
        ingredient[x][y]+= age//2

def fall():
    global trees
    t = list(trees)
    for age,x,y in t:
        if age%5 ==0:
            for i in range(8):
                ny,nx = y+dy[i],x+dx[i]
                if ny<0 or nx<0 or ny>=N or nx>=N: continue
                trees.appendleft((1,nx,ny))

def winter():
    for i in range(N):
        for j in range(N):
            ingredient[i][j] += A[i][j]

for i in range(K):
    dead = spring()

    summer(dead)
    fall()

    winter()
print(len(trees))


###############################################################
###############################################################
###############################################################
###############################################################
###############################################################
###############################################################


N,M,K = map(int,input().split())
A= [list(map(int,input().split())) for _ in range(N)]
trees={(i,j): deque() for i in range(N) for j in range(N)}


# initial sort
tmp=[[[]for _ in range(N)] for _ in range(N)]
for _ in range(M):
    x,y,z= map(int,input().split())
    tmp[x-1][y-1].append(z)

for i in range(N):
    for j in range(N):
        tmp[i][j].sort()
        trees[(i,j)] = deque(tmp[i][j])

ingredient =[[5]*N for _ in range(N)]

dx=[-1,-1,-1,0,0,1,1,1]
dy=[-1,0,1,-1,1,-1,0,1]

# 봄 = 나이만큼 양분 섭취 후 나이++, 나이가 어린 나무부터 양분섭취, 부족할시 즉사
# 여름 = 봄에 죽은 나무나이/2 가 양분으로 추가
# 가을 = 번식, 나무나이가 5의 배수일시 인접한칸에 나무생성
# 겨울 = 양분추가

def spring():
    dead=[]

    for (x,y), ages in trees.items():
        survived = deque()
        for age in ages:
            if ingredient[x][y]<age:
                dead.append((x,y,age))
            else:
                ingredient[x][y]-=age
                survived.append(age+1)
        trees[(x,y)] = survived
    return dead

def summer(dead):
    for x,y,age in dead:
        ingredient[x][y] += age//2

def fall():
    tmp =[[0]*N for _ in range(N)]
    for (x,y), ages in trees.items():
        for age in ages:
            if age%5==0:
                for i in range(8):
                    nx,ny=x+dx[i],y+dy[i]
                    if nx<0 or ny<0 or nx>=N or ny >=N: continue
                    tmp[nx][ny]+=1

    for i in range(N):
        for j in range(N):
            for k in range(tmp[i][j]):
                trees[(i,j)].appendleft(1)


def winter():
    for i in range(N):
        for j in range(N):
            ingredient[i][j] += A[i][j]

def count():
    cnt=0
    for i in range(N):
        for j in range(N):
            cnt += len(trees[(i, j)])
    return cnt
for i in range(K):
    dead = spring()
    summer(dead)
    fall()
    winter()

print(count())

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

문제

문제

출처

ICPC

[파이썬]pypy 시간 초과나는 이유를 잘 모르겠습니다.

wksehfdl8 3년 전 1

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말