[프로그래머스 Lv.2] 행렬 테두리 회전하기 (Python)

문제 링크: https://school.programmers.co.kr/learn/courses/30/lessons/77485?language=python3

프로그래머스

풀이

우선 아래와 같이 우측으로 행렬의 테두리를 회전하도록 풀이해 보았다. 하지만 아래 풀이대로 진행하면 시간 초과가 발생한다. rows와 columns가 100이고, queries도 10000 이하이므로 풀이 로직 상에서는 시간 초과가 발생하지 않을 것이라고 생각하였으나 시간 초과가 발생하여 상당히 당황스러웠었다.

시간 초과 발생 코드

import copy

def solution(rows, columns, queries):        
    # 행렬 생성
    arr = []
    acc = 1
    for i in range(rows):
        sub_arr = []
        for j in range(columns):
            sub_arr.append(acc)
            acc += 1
        arr.append(sub_arr)
    
    answer = []
    for query in queries:
        x1, y1, x2, y2 = query
        
        copy_arr = copy.deepcopy(arr)
        _min = 10001
        # 테두리의 상부 회전
        for i in range(y1, y2 + 1):
            next = i
            pre = copy_arr[x1 - 1][next - 1]

            if next > y2 - 1:
                arr[x1][next - 1] = pre
            else:
                arr[x1 - 1][next] = pre

            _min = min(_min, pre)

        # 테두리의 우측 부분 회전
        for i in range(x1, x2 + 1):
            next = i
            pre = copy_arr[next - 1][y2 - 1]

            if next > x2 - 1:
                arr[next - 1][y2 - 2] = pre

            else:
                arr[next][y2 - 1] = pre

            _min = min(_min, pre)



        # 테두리의 하부 회전
        for i in range(y2, y1 - 1, -1):
            next = i - 2
            pre = copy_arr[x2 - 1][next + 1]

            if next < y1 - 1:
                arr[x2 - 2][next + 1] = pre

            else:
                arr[x2 - 1][next] = pre

            _min = min(_min, pre)

        # 테두리의 좌측 부분 회전
        for i in range(x2, x1 - 1, -1):
            next = i - 2
            pre = copy_arr[next + 1][y1 - 1]

            if next < x1 - 1:
                arr[next + 1][y1] = pre

            else:
                arr[next][y1 - 1] = pre

            _min = min(_min, pre)
        

        answer.append(_min)
        
    return answer

코드를 자세하게 파악해보니 회전 전의 전체 상태를 기억하기 위해 사용하는 deepcopy가 시간을 어마무시하게 잡아먹고 있었기 때문이었다. 구글링을 진행해 보니 slicing을 사용하는 방법보다 무려 100배가량 시간이 더 오래 걸린다고 한다. 그래서 slicing을 사용하는 방법으로 아래와 같이 변경하였고, 시간 초과 없이 문제를 해결할 수 있었다.

def solution(rows, columns, queries):        
    # 행렬 생성
    arr = []
    acc = 1
    for i in range(rows):
        sub_arr = []
        for j in range(columns):
            sub_arr.append(acc)
            acc += 1
        arr.append(sub_arr)
    
    answer = []
    for query in queries:
        x1, y1, x2, y2 = query
        
        copy_arr = [item[:] for item in arr] # 회전 이전 상태를 저장하기 위해 배열의 내용을 copy
        _min = 10001
        # 테두리의 상부 회전
        for i in range(y1, y2 + 1):
            next = i
            pre = copy_arr[x1 - 1][next - 1]

            if next > y2 - 1:
                arr[x1][next - 1] = pre
            else:
                arr[x1 - 1][next] = pre

            _min = min(_min, pre)

        # 테두리의 우측 부분 회전
        for i in range(x1, x2 + 1):
            next = i
            pre = copy_arr[next - 1][y2 - 1]

            if next > x2 - 1:
                arr[next - 1][y2 - 2] = pre

            else:
                arr[next][y2 - 1] = pre

            _min = min(_min, pre)



        # 테두리의 하부 회전
        for i in range(y2, y1 - 1, -1):
            next = i - 2
            pre = copy_arr[x2 - 1][next + 1]

            if next < y1 - 1:
                arr[x2 - 2][next + 1] = pre

            else:
                arr[x2 - 1][next] = pre

            _min = min(_min, pre)

        # 테두리의 좌측 부분 회전
        for i in range(x2, x1 - 1, -1):
            next = i - 2
            pre = copy_arr[next + 1][y1 - 1]

            if next < x1 - 1:
                arr[next + 1][y1] = pre

            else:
                arr[next][y1 - 1] = pre

            _min = min(_min, pre)
        

        answer.append(_min)
        
    return answer