프로그래머스 : 행렬과 연산 [2022 KAKAO TECH INTERNSHIP, 파이썬, 레벨 4]

[본 문제는 정확성과 효율성 테스트 각각 점수가 있는 문제입니다.]

 

당신은 행렬에 적용할 수 있는 두 가지 연산을 만들었습니다.

• ShiftRow
  • 모든 행이 아래쪽으로 한 칸씩 밀려납니다.
  • 즉, 모든 행에 대해서 i번째 행은 i+1번째 행이 됩니다. (마지막 행은 1번째 행이 됩니다.)
  • ShiftRow의 예 

    

    • 왼쪽 행렬이 초기 상태이고 오른쪽 행렬이 ShiftRow를 한 번 시행한 뒤의 행렬입니다.
    • 1번째 행에 있던 [1,2,3]이 2번째 행으로, 2번째 행에 있던 [4,5,6]이 3번째 행으로, 3번째 행에 있던 [7,8,9]가 1번째 행이 된 것을 확인할 수 있습니다.

• Rotate
  • 행렬의 바깥쪽에 있는 원소들을 시계 방향으로 한 칸 회전시킵니다.
  • 행렬의 바깥쪽에 있는 원소들은 첫 행, 첫 열, 끝 행, 끝 열에 포함되는 원소들입니다.
  • 한 칸 회전시킨다는 것은 이 원소들이 시계 방향으로 한 칸씩 밀려난다는 것을 의미합니다. 즉, 다음 4개의 연산이 동시에 시행됩니다.
    • 첫 행에서 끝 열에 있는 원소를 제외한 첫 행의 모든 원소는 오른쪽으로 한 칸 이동합니다.
    • 끝 열에서 끝 행에 있는 원소를 제외한 끝 열의 모든 원소는 아래쪽으로 한 칸 이동합니다.
    • 끝 행에서 첫 열에 있는 원소를 제외한 끝 행의 모든 원소는 왼쪽으로 한 칸 이동합니다.
    • 첫 열에서 첫 행에 있는 원소를 제외한 첫 열의 모든 원소는 위쪽으로 한 칸 이동합니다.
  • Rotate의 예 

    

    • 왼쪽 행렬이 초기 상태이고 오른쪽 행렬이 Rotate를 한 번 시행한 뒤의 행렬입니다.
    • 바깥쪽에 있는 값들이 시계 방향으로 한 칸씩 이동한 것을 확인할 수 있습니다.

당신은 행렬에 연산을 여러 번 시행하려고 합니다.
행렬의 초기 상태를 담고 있는 2차원 정수 배열 rc, 시행할 연산을 순서대로 담고 있는 문자열 배열 operations가 매개변수로 주어졌을 때, 연산을 차례대로 시행한 후의 행렬 상태를 return 하도록 solution 함수를 완성해주세요.

---

제한사항

• 2 ≤ rc의 행 길이(=행렬의 가로 길이) ≤ 50,000
  • rc의 모든 행의 길이는 동일합니다.
• 2 ≤ rc의 열 길이(=행렬의 세로 길이) ≤ 50,000
  • rc의 모든 열의 길이는 동일합니다.
• 4 ≤ rc의 행 길이 x rc의 열 길이 ≤ 100,000
• rc[i][j] 는 i+1번째 행 j+1번째 열에 있는 원소를 나타냅니다.
  • 1 ≤ rc[i][j] ≤ 1,000,000
• 1 ≤ operations의 길이 ≤ 100,000
  • operations의 원소는 "ShiftRow" 혹은 "Rotate"입니다.

정확성 테스트 케이스 제한 사항

• 2 ≤ rc의 행 길이(=행렬의 가로 길이) ≤ 1,000
  • rc의 모든 행의 길이는 동일합니다.
• 2 ≤ rc의 열 길이(=행렬의 세로 길이) ≤ 1,000
  • rc의 모든 열의 길이는 동일합니다.
• 4 ≤ rc의 행 길이 x rc의 열 길이 ≤ 10,000
• 1 ≤ operations의 길이 ≤ 100

효율성 테스트 케이스 제한 사항

• 주어진 조건 외 추가 제한사항 없습니다.

---

입출력 예

rc	operations	result
[[1, 2, 3], [4, 5, 6], [7, 8, 9]]	["Rotate", "ShiftRow"]	[[8, 9, 6], [4, 1, 2], [7, 5, 3]]
[[8, 6, 3], [3, 3, 7], [8, 4, 9]]	["Rotate", "ShiftRow", "ShiftRow"]	[[8, 3, 3], [4, 9, 7], [3, 8, 6]]
[[1, 2, 3, 4], [5, 6, 7, 8], [9, 10, 11, 12]]	["ShiftRow", "Rotate", "ShiftRow", "Rotate"]	[[1, 6, 7 ,8], [5, 9, 10, 4], [2, 3, 12, 11]]

---

입출력 예 설명

입출력 예#1

위 그림은 ”Rotate”와 ”ShiftRow”를 차례대로 실행한 결과입니다.

따라서 [[8, 9, 6], [4, 1, 2], [7, 5, 3]]을 return 해야 합니다.

 

입출력 예#2

위 그림은 ”Rotate”, ”ShiftRow”, "ShiftRow"를 차례대로 실행한 결과입니다.

따라서 [[8, 3, 3], [4, 9, 7], [3, 8, 6]]을 return 해야 합니다.

 

 

 

1. 처음에 그대로 구현한 코드. ShiftRow 연산은 그대로 구현하면 모든 원소를 움직여야하기때문에 행*열*연산수의 시간이 걸린다.

=> 효율성 테스트 통과 불가능! (근데 컴파일 에러도 났다. 도중에 깨닫고 다른 방법으로 시도)

import copy

def solution(rc, operations):
    answer = [] # result array
    rowNum = len(rc)
    columnNum = len(rc[0])
    for op in operations:
        if op=="ShiftRow":
            answer.append(rc[len(rc)-1])
            for i in range(len(rc)-1):
                answer.append(rc[i])
            rc = copy.deepcopy(answer)
            answer=[]
        elif op=="Rotate":
            rcCopy = copy.deepcopy(rc)
            # 0 row
            for i in range(rowNum-2):
                rc[0][i+1]=rcCopy[0][i]
            # 0 column
            for i in range(rowNum-2):
                rc[i][0]=rcCopy[i+1][0]
            # Length row
            for i in range(rowNum-2):
                rc[columnNum-1][i]=rcCopy[columnNum-1][i+1]
            # Length column
            for i in range(rowNum-2):
                rc[i+1][rowNum-1]=rcCopy[i][columnNum-1]
    answer = copy.deepcopy(rc)
        
    return answer
print(solution([[1, 2, 3, 4], [5, 6, 7, 8], [9, 10, 11, 12]], ["ShiftRow", "Rotate", "ShiftRow", "Rotate"]))

 

2. 원소를 행별로, 가장자리 원소별로 관리하는 방법을 사용해 효율성 테스트를 통과한다!

1	1	1	1	1
2	2	2	2	2
3	3	3	3	3
4	4	4	4	4
5	5	5	5	5

(위와 같이 가장자리끼리, 안쪽의 행 111,222,333,444,555 끼리)

 

바깥쪽 열 2줄, 행2줄에서 각각 하나의 원소만 옮기기 때문에 O(1)의 시간만이 소요된다.

 

주석으로 설명 대체 (+ 나중에 더 자세히 수정예정)

# 데크: 앞, 뒤 양쪽 방향에서 엘리먼트(element)를 추가하거나 제거, 행과 가장자리 열 관리에 사용할 것
from collections import deque 

def solution(rc, operations):
    rowNum, colNum = len(rc), len(rc[0]) # 행의 수, 열의 수
    
    # ShiftRow 연산을 위해 행별로 관리 => 양쪽 원소를 제외한 행
    rows = deque(deque(row[1:-1]) for row in rc)
    
    # Rotate 연산을 위해 바깥쪽 원소들(열별)을 관리 [첫열, 마지막열]
    out_cols = [deque(rc[r][0] for r in range(rowNum)),
                deque(rc[r][colNum - 1] for r in range(rowNum))]

    # 연산
    for operation in operations:
        if operation[0] == "S": # ShiftRow 연산
            # 마지막(가장 아래) 행을 처음(가장 위)로 이동
            rows.appendleft(rows.pop())
            # 첫 열과 마지막 열의 마지막(가장 아래) 원소를 처음(가장 위)으로 이동
            out_cols[0].appendleft(out_cols[0].pop())
            out_cols[1].appendleft(out_cols[1].pop())
        
        else: # Rotate 연산, 4개만 처리하면 됨. 
            # *** rows가 비어있을 수 있기 때문에 순서 주의 ***
            # 마지막 열의 마지막(가장 아래) 원소를 마지막 행의 마지막(가장 오른쪽)으로 이동
            rows[rowNum - 1].append(out_cols[1].pop())
            # 마지막 행의 첫(가장 왼쪽) 원소를 첫 열의 마지막(가장 아래)으로 이동
            out_cols[0].append(rows[rowNum - 1].popleft())
            # 첫 열의 첫(가장 위) 원소를 첫 행의 처음(가장 왼쪽)으로 이동
            rows[0].appendleft(out_cols[0].popleft())
            # 첫 행의 마지막(가장 오른쪽) 원소를 마지막 열의 처음(가장 위)으로 이동
            out_cols[1].appendleft(rows[0].pop())
            
    
    answer = []
    for r in range(rowNum):
        answer.append([])
        answer[r].append(out_cols[0][r])
        answer[r].extend(rows[r])
        answer[r].append(out_cols[1][r]) 
    
    return answer