[Programmers] P118670 행렬과 연산

[Programmers] P118670 행렬과 연산

Question

Language: Python

shift_row 나 rotate와 같은 행렬 연산 자체는 간단한 연산이다.

하지만, row,col, operation이 많은 상황에서는 단순히 모든 연산을 list 형태로 처리하면은 시간초과가 발생하게 된다.

가령 아래와 같이 수행하게 되면, 내부적으로 최대 (n_rows-1) 만큼의 이동이 발생한다.

위의 시간 복잡도는 O(R)

rows=[...]
rows.insert(0,rows.pop())

또한, rotate 에 대해서도, 모든 테두리에 있는 row,col에 일일히 처리하게 된다면 n_cols*2 + (n_row-2)*2 만큼의 연산이 매번 수행된다.

시간 복잡도는 O(R+C)

총 시간 복잡도는 O(N*(R+C))로 매우 무거운 연산으로 시간 초과가 발생한다.

Deque을 통한 matrix을 분해

그렇기 때문에 행렬간에 연산을 처리할 때 아래와 같이 deque()를 활용해서 O(1) 시간 복잡도로 연산을 처리할 수 있도록 한다.

rotate의 경우에는 아래와 같이 생각해볼 수 있다.

Solution

from collections import deque

def shift_rows(left_col,middle_rows,right_col):
    #왼쪽 열
    left_col.appendleft(left_col.pop())
    #중간 행
    middle_rows.appendleft(middle_rows.pop())
    #오른쪽 열
    right_col.appendleft(right_col.pop())
    
def rotate(left_col,middle_rows,right_col):
    #왼쪽 모서리 위
    middle_rows[0].appendleft(left_col.popleft())
    #오른쪽 모서리 위
    right_col.appendleft(middle_rows[0].pop())
    #오른쪽 모서리 아래
    middle_rows[-1].append(right_col.pop())
    #왼쪽 모서리 아래
    left_col.append(middle_rows[-1].popleft())

def solution(rc, operations):
    
    
    n_rows=len(rc)
    n_cols=len(rc[0])
    
    left_col=deque()
    middle_rows=deque()
    right_col=deque()
    
    #deque 집합으로 만드는 과정
    for row in rc:
        left_col.append(row[0])
        middle_rows.append(deque(row[1:-1]))
        right_col.append(row[-1])
    #operation 처리
    for operation in operations:
        if operation=="Rotate":
            rotate(left_col,middle_rows,right_col)
        else:
            shift_rows(left_col,middle_rows,right_col)
    
    answer = [[0]*n_cols for _ in range(n_rows)]
    
    #다시 배열로 만들기
    for row in range(n_rows):
        answer[row][0]=left_col.popleft()
        answer[row][-1]=right_col.popleft()
        queue=middle_rows.popleft()
        for col in range(1,n_cols-1):
            answer[row][col]=queue.popleft()  
            
    return answer

Reference

공채 해설