글 읽기 - 시간복잡도 개선

lesk012 1년 전 0

for 문이 3중이라 시간초과를 예상했지만,

이렇게 완전탐색 하지 않고 해결할 방법이 있는지 궁금합니다.

import sys

R, C, T = map(int, sys.stdin.readline().split())
origin_matrix = []
copy_matrix = []
for _ in range(R):
    origin_matrix.append(list(map(int, sys.stdin.readline().split())))
    copy_matrix.append([0] * C)

air_cleaner = []  # x 좌표만 저장
dust_pos = []

for r in range(R):
    for c in range(C):
        if origin_matrix[r][c] != 0:
            if origin_matrix[r][c] == -1:
                air_cleaner.append(r)
            else:
                dust_pos.append((r, c))

for _ in range(T):
    # <diffusion>
    for d_pos in dust_pos:
        possible_dir_cnt = 0
        possible_dir_pos = []
        x = d_pos[0]
        y = d_pos[1]

        if 0 <= x - 1 < R and 0 <= y < C:
            if y == 0:
                if x - 1 != air_cleaner[0] and x - 1 != air_cleaner[1]:
                    possible_dir_cnt += 1
                    possible_dir_pos.append((x - 1, y))
            else:
                possible_dir_cnt += 1
                possible_dir_pos.append((x - 1, y))
        if 0 <= x + 1 < R and 0 <= y < C:
            if y == 0:
                if x + 1 != air_cleaner[0] and x + 1 != air_cleaner[1]:
                    possible_dir_cnt += 1
                    possible_dir_pos.append((x + 1, y))
            else:
                possible_dir_cnt += 1
                possible_dir_pos.append((x + 1, y))
        if 0 <= x < R and 0 <= y - 1 < C:
            if y - 1 == 0:
                if x != air_cleaner[0] and x != air_cleaner[1]:
                    possible_dir_cnt += 1
                    possible_dir_pos.append((x, y - 1))
            else:
                possible_dir_cnt += 1
                possible_dir_pos.append((x, y - 1))
        if 0 <= x < R and 0 <= y + 1 < C:
            if y + 1 == 0:
                if x != air_cleaner[0] and x != air_cleaner[1]:
                    possible_dir_cnt += 1
                    possible_dir_pos.append((x, y + 1))
            else:
                possible_dir_cnt += 1
                possible_dir_pos.append((x, y + 1))

        if possible_dir_cnt:
            dust = origin_matrix[x][y] // 5
            for pos in possible_dir_pos:
                copy_matrix[pos[0]][pos[1]] += dust
            origin_matrix[x][y] -= dust * possible_dir_cnt
        possible_dir_cnt = 0
        possible_dir_pos.clear()

    # <original += copy>
    for r in range(R):
        for c in range(C):
            if copy_matrix[r][c] != 0 and copy_matrix[r][c] != -1:
                origin_matrix[r][c] += copy_matrix[r][c]
    copy_matrix.clear()
    for _ in range(R):  # reset
        copy_matrix.append([0] * C)

    # <move>
    # counterclockwise: start at air_cleaner[0]
    # 1) left
    for x in range(air_cleaner[0] - 2, -1, -1):
        origin_matrix[x + 1][0] = origin_matrix[x][0]
    # 2) up
    for y in range(1, C):
        origin_matrix[0][y - 1] = origin_matrix[0][y]
    # 3) right
    for x in range(1, air_cleaner[0] + 1):
        origin_matrix[x - 1][C - 1] = origin_matrix[x][C - 1]
    # 4) down
    for y in range(C - 2, 0, -1):
        origin_matrix[air_cleaner[0]][y + 1] = origin_matrix[air_cleaner[0]][y]
    origin_matrix[air_cleaner[0]][1] = 0  # 젤 마지막 0 채우기

    # clockwise: start at air_cleaner[1]
    # 1) left
    for x in range(air_cleaner[1] + 2, R):
        origin_matrix[x - 1][0] = origin_matrix[x][0]
    # 2) down
    for y in range(1, C):
        origin_matrix[R - 1][y - 1] = origin_matrix[R - 1][y]
    # 3) right
    for x in range(R - 2, air_cleaner[1] - 1, -1):
        origin_matrix[x + 1][C - 1] = origin_matrix[x][C - 1]
    # 4) up
    for y in range(C - 2, 0, -1):
        origin_matrix[air_cleaner[1]][y + 1] = origin_matrix[air_cleaner[1]][y]
    origin_matrix[air_cleaner[1]][1] = 0  # 젤 마지막 0 채우기

    # update dust_pos
    dust_pos.clear()
    for r in range(R):
        for c in range(C):
            if origin_matrix[r][c] != 0 and origin_matrix[r][c] != -1:
                dust_pos.append((r, c))

dust_sum = 2 #공기청정기 있는 칸이 -1씩 이므로
for row in origin_matrix:
    dust_sum += sum(row)
print(dust_sum)

bug_hunter 1년 전 0

저는 혹시 배열을 이중 for문 돌면서 갱신하는 게 느린가 해서 다른 방식으로 풀어봤는데,

계속 python3은 시간초과 나다가, pypy3로 하니 바로 되더라고요.

@lesk012 님의 코드도 pypy3로 제출하니까 통과되네요.

38번 줄부터는 시간 측정 코드 빼고는 lesk012님 코드 그대로입니다.

검색을 해봤는데 파이썬에서 배열 깊은 복사는 리스트 슬라이싱이 빠르다고 하더군요.

파이썬 얕은 복사와 깊은 복사 관련하여 검색해보시면 좋을 것 같네요🥰

import sys
import time

#start = time.time()

R, C, T = map(int, sys.stdin.readline().split())
origin_matrix = []
for _ in range(R):
    origin_matrix.append(list(map(int, sys.stdin.readline().split())))

air_cleaner = []  # x 좌표만 저장

for r in range(R):
    for c in range(C):
        if origin_matrix[r][c] == -1:
            air_cleaner.append(r)

for _ in range(T):
    # <diffusion>
    new_matrix = [row[:] for row in origin_matrix] # 리스트 슬라이싱을 이용한 깊은 복사
    for i in range(R):
        for j in range(C):
            dust = origin_matrix[i][j]
            if dust == -1:
                continue
            for pos in [(i + 1, j), (i, j + 1), (i - 1, j), (i, j - 1)]:
                ni, nj = pos
                if 0 <= ni < R and 0 <= nj < C and origin_matrix[ni][nj] != -1:
                    cust = dust // 5 # 의미없는 변수명입니다. abc<-de...
                    new_matrix[ni][nj] += cust;
                    new_matrix[i][j] -= cust;

    # 새 matrix로 바꾸는 식들인데 큰 차이는 없는 것 같네요.
#    origin_matrix = new_matrix
#    origin_matrix = new_matrix.copy()
    origin_matrix, new_matrix = new_matrix, origin_matrix

    # <move>
    # counterclockwise: start at air_cleaner[0]
    # 1) left
    for x in range(air_cleaner[0] - 2, -1, -1):
        origin_matrix[x + 1][0] = origin_matrix[x][0]
    # 2) up
    for y in range(1, C):
        origin_matrix[0][y - 1] = origin_matrix[0][y]
    # 3) right
    for x in range(1, air_cleaner[0] + 1):
        origin_matrix[x - 1][C - 1] = origin_matrix[x][C - 1]
    # 4) down
    for y in range(C - 2, 0, -1):
        origin_matrix[air_cleaner[0]][y + 1] = origin_matrix[air_cleaner[0]][y]
    origin_matrix[air_cleaner[0]][1] = 0  # 젤 마지막 0 채우기

    # clockwise: start at air_cleaner[1]
    # 1) left
    for x in range(air_cleaner[1] + 2, R):
        origin_matrix[x - 1][0] = origin_matrix[x][0]
    # 2) down
    for y in range(1, C):
        origin_matrix[R - 1][y - 1] = origin_matrix[R - 1][y]
    # 3) right
    for x in range(R - 2, air_cleaner[1] - 1, -1):
        origin_matrix[x + 1][C - 1] = origin_matrix[x][C - 1]
    # 4) up
    for y in range(C - 2, 0, -1):
        origin_matrix[air_cleaner[1]][y + 1] = origin_matrix[air_cleaner[1]][y]
    origin_matrix[air_cleaner[1]][1] = 0  # 젤 마지막 0 채우기

dust_sum = 2 #공기청정기 있는 칸이 -1씩 이므로
for row in origin_matrix:
    dust_sum += sum(row)
print(dust_sum)

#print(time.time() - start, "sec")

lesk012 1년 전 1

와 정말 그렇네요 ...

오랜만에 해서 pypy로 돌려볼 생각을 못했습니다 ㅎㅎ

이번에도 역시 감사해요 @bug_hunter 님 :)

lesk012 1년 전 0

아 그리고 덕분에 파이썬 복사에 대해 자세히 알게 되었습니다. 감사해요 ㅎㅎㅎ

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

문제

문제

출처

ICPC

시간복잡도 개선

lesk012 1년 전 0

bug_hunter 1년 전 0

lesk012 1년 전 1

lesk012 1년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말