[프로그래머스] 행렬과 연산

https://school.programmers.co.kr/learn/courses/30/lessons/118670

프로그래머스

1. 문제설명

• 행렬이 주어질 때 operations (Rotate, ShiftRow)를 순서대로 실행한 후 행렬의 결과 반환

 

2. 문제해결

[첫번째 코드]

def solution(rc, operations):
    from collections import deque
    new_rc = deque([])
    for r in rc:
        new_rc.append(deque(r))
    row_len = len(rc)
    
    for operation in operations:
        if operation == "Rotate":
            for i in range(row_len - 1):
                a = new_rc[i+1].popleft()
                new_rc[i].appendleft(a)
                
                j = row_len-1-i
                b = new_rc[j-1].pop()
                new_rc[j].append(b)
        else:
            n = 0
            while n < row_len-1:
                cur_rc = new_rc.popleft()
                new_rc.append(cur_rc)
                n += 1
    result = []
    for r in new_rc:
        result.append(list(r))
    return result

• 정확성은 100점이지만 효율성에서 0점이 나왔다.
  • operations의 최대 길이가 10^5, row_len의 최대 길이가 5*10^4니까 당연히 2중 for문 돌리면 시간 초과 발생
  • operations은 무조건 for문을 돌려야 한다. 그러면 for문 없이 “Rotate”, “ShiftRow”를 처리하는 방법 !?
• 행렬의 구성을 바꿔보자 !
  • 문제에서 rc가 [[1, 2, 3], [4, 5, 6], [7, 8, 9]]일 때 그대로 쓰면 [1, 2, 3] → [4, 5, 6] → [7, 8, 9] 처럼 for문이 필요할 수밖에 없다.
  • Rotate의 핵심은 “열”이 바뀌는 것이니까 start, mid, end로 나눠서 처리해보자.

 

[두번째 코드]

def solution(rc, operations):
    from collections import deque
    row_len = len(rc)
    col_len = len(rc[0])
    
    # 새로운 행렬 형태 만들기
    start = deque()
    mid = deque()
    end = deque()
    for i in range(len(rc)):
        start.append(rc[i][0])
        mid.append(deque(rc[i][1:col_len-1]))
        end.append(rc[i][col_len-1])

    for op in operations:
        # 각 열끼리(start, mid, end) 행 순서에 따라 저장되어 있으므로 rotate를 실행하면 자동으로 행 변환
        if op == "ShiftRow":
            start.rotate()
            mid.rotate()
            end.rotate()
            
        # for문 필요 없이 열(start, mid, end)이 바뀌는 부분만 보면 된다. 
        elif op == "Rotate":
            # 1. start -> mid
            mid[0].appendleft(start.popleft())
            # 2. mid -> end
            end.appendleft(mid[0].pop())
            # 3. end -> mid
            mid[row_len-1].append(end.pop())
            # 4. mid -> start
            start.append(mid[row_len-1].popleft())
            
    result = []
    for i in range(len(rc)):
        result.append([start[i]] + list(mid[i]) + [end[i]])
    return result

• for문 없이 어떻게 돌려 ???? 싶었는데 ShiftRow는 rorate 함수로 처리하면 되고, Rotate는 열이 바뀌는 (예를 들어, start에서 mid로 이동) 부분만 pop & append 해주면 된다.