[구현] 행렬 테두리 회전하기

달팽이 문제에서 따온 발상 이용해서 구현

import copy
def solution(rows, columns, queries):
    # 초기 사각형 만들기
    grid = []
    num = 0
    
    for _ in range(rows):
        t = []
        for _ in range(columns):
            num += 1
            t.append(num)
        grid.append(t)
    
    answer = []
    
    # 쿼리받는 반복문
    for q in queries:
        ogrid = copy.deepcopy(grid) # 전단계의 grid를 저장해둔다
        x1, y1, x2, y2 = q 
        x1, y1, x2, y2 = x1-1, y1-1, x2-1, y2-1 # 위치를 변경할 사각형의 꼭짓점(인덱스 위해 -1)

        w = y2-y1 # width
        h = x2-x1 # heigth
        
        loop = [range(w), range(h), range(w), range(h)]
        
        x, y = x1, y1
        result = int(1e9)
        
        o_former_val = 0
        for i in range(4): # 우 하 좌 상
            for ii in loop[i%4]:
                former_x, former_y = x, y # 전 단계의 값 저장
                # print('former x y', former_x, former_y)
                # print('former value', ogrid[former_x][former_y])
                o_former_val = grid[x][y]
                if ogrid[former_x][former_y] < result:
                    result = ogrid[former_x][former_y]
                if i%4 == 0:
                    y += 1
                    grid[x][y] = ogrid[former_x][former_y]
                    
                elif i%4 == 1:
                    former_x = x
                    x += 1
                    grid[x][y] = ogrid[former_x][former_y]
                    
                elif i%4 == 2:
                    former_y = y
                    y -= 1
                    grid[x][y] = ogrid[former_x][former_y]
                    
                elif i%4 == 3:
                    former_x = x
                    x -= 1
                    grid[x][y] = ogrid[former_x][former_y]
                
        answer.append(result)
        # print(w)
        # for i in grid:
        #     print(i)
        # print('-'*20)
    return answer

그러나 테두리를 따라서 바꾸면서 움직이다보면 전단계의 값이 원래 값이 아니라 덮어씌어진 값이기때문에 처음 바뀐 값으로 모든 테두리 값이 변경된다.

그래서 전단계의 grid를 ogrid로 따로 저장해두고 쓸 수 밖에 없었는데 당연히 매우 큰 행렬 두개를 만드는 건 너무 비효율적이었고 시간 초과가 뜬다.

어떻게 해결할까?

두개의 변수로 현재원래값(ooval)과 전단계의 원래값(oval) 저장. 현단계에서 전단계의 원래값으로 바꿨으면 전단계의 원래값(oval)을 현재원래값(ooval)으로 변경

def solution(rows, columns, queries):
    # 초기 사각형 만들기
    grid = []
    num = 0
    
    for _ in range(rows):
        t = []
        for _ in range(columns):
            num += 1
            t.append(num)
        grid.append(t)
    
    answer = []
    
    # 쿼리받는 반복문
    for q in queries:
        # ogrid = copy.deepcopy(grid) # 전단계의 grid를 저장해둔다
        x1, y1, x2, y2 = q 
        x1, y1, x2, y2 = x1-1, y1-1, x2-1, y2-1 # 위치를 변경할 사각형의 꼭짓점(인덱스 위해 -1)
        w = y2-y1 # width
        h = x2-x1 # heigth
        
        loop = [range(w), range(h)]*2
        
        x, y = x1, y1
        result = int(1e9)
        
        oval = grid[x][y] # 전단계의 orginal value
        for i in range(4): # 우 하 좌 상
            for ii in loop[i%4]: 
                if  oval < result:
                    result = oval
                if i%4 == 0:
                    y += 1
                    
                elif i%4 == 1:
                    former_x = x
                    x += 1
                    
                elif i%4 == 2:
                    former_y = y
                    y -= 1
                      
                elif i%4 == 3:
                    former_x = x
                    x -= 1
                    
                ooval = grid[x][y] # 지금단계의 original_value
                grid[x][y] = oval # 전단계의 original_value
                oval = ooval 
                
        answer.append(result)
    return answer