[프로그래머스] python3 - 행렬 테두리 회전하기

프로그래머스 level 2 - 행렬 테두리 회전하기

- python3 : deepcopy와 slicing copy 속도 차이 -

 

프로그래머스 level 2 - 행렬 테두리 회전하기

1. 요구사항

자세한 설명은 프로그래머스 참고

 

2. 문제 해결법

 - 주어진 회전 목록 queries에 따라 각 좌표를 이동시킨 후, 이동한 좌표의 값들 중 최소 값을 배열에 담으면 된다.

 

 1) graph 행렬 생성

 2) 회전 목록마다 좌표 이동 (이 때, temp 라는 깊은 복사 그래프를 만들어서 끝부분이 안 겹치도록 함)

 3) 이동할 때마다 해당 값을 nums 배열에 저장

 4) 이동이 끝난 후, nums의 최소값을 result 배열에 저장

 5) 이동된 temp 그래프를 graph로 얕은 복사

 6) *회전 목록이 끝날 때까지 2번부터 반복

 7) result 배열 출력

 

3. 키 포인트

 - 처음에 deepcopy로 풀었는데, 시간 초과가 나서 slicing을 이용한 복사 방법으로 시간 단축

 

[방법1. deepcopy (시간초과)]

import copy

def solution(rows, columns, queries):
    graph = [[0] * columns for _ in range(rows)]
    num = 0
    for i in range(rows):
        for j in range(columns):
            num += 1
            graph[i][j] = num
    
    result = []
    for q in queries:
        [r1,c1,r2,c2] = q
        r1 -= 1
        c1 -= 1
        r2 -= 1
        c2 -= 1
        temp = copy.deepcopy(graph)
        nums = []
        for i in range(c1, c2):
            nums.append(graph[r1][i])
            nums.append(graph[r2][i+1])
            temp[r1][i+1] = graph[r1][i]
            temp[r2][i] = graph[r2][i+1]
        for j in range(r1, r2):
            nums.append(graph[j][c2])
            nums.append(graph[j+1][c1])
            temp[j+1][c2] = graph[j][c2]
            temp[j][c1] = graph[j+1][c1]
        
        graph = temp
        result.append(min(nums))
    
    return result

 

[방법2. slicing 복사 (통과) ]

def solution(rows, columns, queries):
    graph = [[0] * columns for _ in range(rows)]
    num = 0
    for i in range(rows):
        for j in range(columns):
            num += 1
            graph[i][j] = num
    
    result = []
    for q in queries:
        [r1,c1,r2,c2] = q
        r1 -= 1
        c1 -= 1
        r2 -= 1
        c2 -= 1
        temp = [item[:] for item in graph]
        nums = []
        for i in range(c1, c2):
            nums.append(graph[r1][i])
            nums.append(graph[r2][i+1])
            temp[r1][i+1] = graph[r1][i]
            temp[r2][i] = graph[r2][i+1]
        for j in range(r1, r2):
            nums.append(graph[j][c2])
            nums.append(graph[j+1][c1])
            temp[j+1][c2] = graph[j][c2]
            temp[j][c1] = graph[j+1][c1]
        
        graph = temp
        result.append(min(nums))
    
    return result

 

4. deepcopy와 slicing 깊은 복사 방법의 차이

 1. deepcopy 복사

   - 객체의 모든 속성과 데이터를 복사하며, 모듈을 불러오는 시간도 포함되어 느리다.

from copy import deepcopy

list1 = [[1] * 10 for _ in range(10)]
list2 = deepcopy(list1)

 2. slicing 복사

   - 리스트의 값만 복사하기 위함이라면, slicing이 deepcopy보다 많게는 100배 이상 속도가 빠르다.

list1 = [[1] * 10 for _ in range(10)]
list2 = [item[:] for item in list1]

 

결론

"빠르게 리스트를 깊은 복사해야할 경우, slicing 복사를 활용"

 

 

 

 

https://programmers.co.kr/learn/courses/30/lessons/77485

코딩테스트 연습 - 행렬 테두리 회전하기