글 읽기 - 혹시 어디서 시간을 더 단축 시킬 수 있는지 알려주실 수 있나요?

grapecw 2년 전 0

나무를 딕셔너리에 키를 좌표로 하여 나무들을 저장했습니다.

봄에 나무를 뽑아서 여름에 있을 죽는 나무를 dieTree에 저장했고 가을에 있을 번식을 하는 나무는 prduction에 넣어서 가을이나 겨울때 따로 계산할 필요가 없게 하였습니다.

혹시 어디에서 시간을 더 단축 시킬 수 있는지 알려주실 수 있으십니까?

import sys
import heapq

input = sys.stdin.readline

spred = ((-1, -1), (-1, 0), (-1, 1), (0, -1), (0, 1), (1, -1), (1, 0), (1, 1))

"""
해당 나무 리스트에 한 해에 처리되는 경우
"""
def oneYearAgo(trees, arc):
    prduction = {}      # 번식 할 나무의 수
    for item in trees:
        # 봄
        area = trees[item]  # (item[0], item[1]) 자리에 심어 있는 나무 리스트
        reIn = []   # 영양을 빨아드린 나무
        dieTree = 0     # 죽은 나무 -> 즉 다시 영양분으로 바"뀔 수치
        while area:
            tree = heapq.heappop(area)
            if arc[item[0]][item[1]] >= tree:
                arc[item[0]][item[1]] -= tree
                heapq.heappush(reIn, tree + 1)
                if (tree + 1) % 5 == 0:
                    if not (item[0], item[1]) in prduction:
                        prduction[(item[0], item[1])] = 1
                    else:
                        prduction[(item[0], item[1])] += 1
            else:
                dieTree += tree // 2
        trees[item] = reIn    # 해당 좌표에 현재 살아 있는 나무를 다시 대입
        # 여름
        arc[item[0]][item[1]] += dieTree
    # 가을
    for item in prduction:
        for next in spred:
            nextY = next[0] + item[0]
            nextX = next[1] + item[1]
            if nextY <= 0 or nextX <= 0 or nextY > n or nextX > n:
                continue
            for _ in range(prduction[item]):
                if not (nextY, nextX) in trees:
                    trees[(nextY, nextX)] = [1]
                else:
                    heapq.heappush(trees[(nextY, nextX)], 1)
    # 겨울
    for i in range(n):
        for j in range(n):
            arc[i + 1][j + 1] += a[i + 1][j + 1]


if __name__ == "__main__":
    n, m, k = map(int, input().strip().split())
    a = [[0] * (n + 1) for _ in range(n + 1)]
    arc = [[5] * (n + 1) for _ in range(n + 1)]
    trees = {}
    for i in range(n):
        inputLine = list(map(int, input().strip().split()))
        for j in range(n):
            a[i + 1][j + 1] = inputLine[j]
    inputLine = None
    for _ in range(m):
        x, y, age = map(int, input().strip().split())
        if not (y, x) in trees:
            trees[(y, x)] = [age]
        else:
            heapq.heappush(trees[(y, x)], age)

    for _ in range(k):
        oneYearAgo(trees, arc)
    treeCnt = 0
    for item in trees:
        treeCnt += len(trees[item])
    print(treeCnt)

owell 2년 전 0

heapq를 사용하면 원소를 넣거나 뺄 때마다 내부에서 정렬이 이뤄져서 시간 초과가 발생하는 것 같습니다. heapq를 사용하지말고 리스트를 이용하되

리스트는 나무들을 입력 받은 후 시뮬레이션이 시작하기 전에 한번만 정렬해주고 새로 자라나는 나무들이 리스트의 맨 앞에 삽입되도록 한다면 오름차순으로 계속 유지됩니다.

저는 봄이 시작할때만 정렬해주었는데도 시간 초과가 나지 않은 걸 보니, 힙 사용이 문제가 되는 것 같습니다.

grapecw 2년 전 0

owell

감사합니다. deque()를 통해 넣고 빼는 시간 단축시키고, 해시 맵에 키가 있는지 없는지 확인 하는 부분을 한번만 확인하게 하니 통과되었습니다.

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

문제

문제

출처

ICPC

혹시 어디서 시간을 더 단축 시킬 수 있는지 알려주실 수 있나요?

grapecw 2년 전 0

owell 2년 전 0

grapecw 2년 전 0

owell

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말