[2022 KAKAO TECH INTERNSHIP 코딩테스트] - 행렬과 연산 (Python) 풀이

들어가며

아래 문제 설명은 풀이를 쉽게 이해할 수 있도록 프로그래머스의 내용을 그대로 인용했음을 밝힙니다. 정확한 자료는 아래 링크를 참고하시기 바랍니다.

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

프로그래머스

문제 설명

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

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

• 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

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

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

풀이

1. 방향 잡기

이 문제의 핵심은 operation을 어떻게 수행할 것인가에 초점이 맞추어져 있습니다. "ShiftRow" 혹은 "Rotate" 는 가장 쉽게 행렬을 조작하여 문제를 푼다면 각각 O(rc의 행 길이 x rc의 열 길이), O(rc의 행 길이 + rc의 열 길이) 만큼의 시간이 소요됩니다. 따라서 전체 소요 시간은 O(rc의 행 길이 x rc의 열 길이 x operations의 길이)로 정확성 테스트의 경우 약 1,000,000의 숫자가 나와 쉽게 해결할 수 있습니다. 그러나 이 알고리즘을 효율성 테스트에 적용할 경우 10,000,000,000 이라는 터무니 없는 숫자 때문에 해결하기가 어렵습니다. 

 

operation의 길이는 불변이므로 우리는 "ShiftRow" 혹은 "Rotate"의 시간복잡도가 O(1) 또는 O(log(rc의 행 길이 x rc의 열 길이 ))으로 개선해야 할 것입니다.

2. Operation 개선

2.1 자료구조 변경

결론부터 말하면 "ShiftRow", "Rotate"을 O(1) 로 개선하는 방법이 있습니다.

첫 번째로, 기존의 Matrix를 left line, middle 그리고 right line으로 나눕니다. 그리고 각 라인은 dequeue로 변경합니다. middle의 내부에 있는 각 row 또한 dequeue로 변경합니다.

def splitLine(self, matrix):
    leftLine=deque()
    rightLine=deque()
    middles = deque()
    for row in range(len(matrix)):
        leftLine.append(matrix[row][0])
        rightLine.append(matrix[row][-1])
        middles.append(deque(matrix[row][1:-1]))
    return leftLine,rightLine,middles

이렇게 하면 ShiftRow와 Rotate를 간단하게 구현할 수 있습니다.

2.1 ShiftRow

먼저 ShiftRow가 입력된 경우 아래와 같이 모든 라인의 dequeue는 마지막 원소를 앞에 오도록 이동합니다. 

def shiftRow(self):
    self.leftLine.appendleft(self.leftLine.pop())
    self.rightLine.appendleft(self.rightLine.pop())
    self.middles.appendleft(self.middles.pop())

2.3 Rotate

Rotate는 아래 4과정으로 다시 표현할 수 있습니다.

1.  왼쪽 위 모서리의 원소가 오른쪽으로 원소들을 밀어냅니다.

2. 오른쪽 위 모서리의 원소가 아래쪽으로 원소들을 밀어냅니다.

3. 오른쪽 아래 모서리의 원소가 왼쪽으로 원소들을 밀어냅니다.

4. 왼쪽 아래 모서리의 원소가 위쪽으로 원소들을 밀어냅니다.

 

요점은 실제로 테두리에 있는 모든 원소들이 이동하는 것이 아니라, 모서리에 있는 각 원소들이 근처의 원소들을 밀어낸다는 것으로 표현하는 것입니다. 이것은 dequeue를 이용해서 가장 간단하게 아래처럼 구현할 수 있습니다. (사실 이 아이디어 때문에 dequeue를 사용하기로 결정했습니다.) 아래 함수를 보시면 알겠지만 위 4과정을 그대로 표현하고 있습니다.

def rotate(self):
    self.middles[0].appendleft(self.leftLine.popleft())
    self.rightLine.appendleft(self.middles[0].pop())
    self.middles[-1].append(self.rightLine.pop())
    self.leftLine.append(self.middles[-1].popleft())

2.4 변경된 자료구조 복구

지금까지 operation 효율을 위해 dequeue를 여러개 사용하여 matrix를 다루었습니다. 그러나 결괏값은 이중 배열 형식이기 때문에 아래와 같이 자료구조를 변경하는 코드를 추가합니다.

def getMatrix(self):
    ret=[]
    for idx in range(len(self.middles)):
        self.middles[idx].appendleft(self.leftLine[idx])
        self.middles[idx].append(self.rightLine[idx])
        ret.append(list(self.middles[idx]))
    return ret

 

전체 코드

from collections import deque


class Matrix:
    def __init__(self, matrix):
        self.leftLine, self.rightLine, self.middles = self.splitLine(matrix)
    def shiftRow(self):
        self.leftLine.appendleft(self.leftLine.pop())
        self.rightLine.appendleft(self.rightLine.pop())
        self.middles.appendleft(self.middles.pop())
    def rotate(self):
        self.middles[0].appendleft(self.leftLine.popleft())
        self.rightLine.appendleft(self.middles[0].pop())
        self.middles[-1].append(self.rightLine.pop())
        self.leftLine.append(self.middles[-1].popleft())

    def getMatrix(self):
        ret=[]
        for idx in range(len(self.middles)):
            self.middles[idx].appendleft(self.leftLine[idx])
            self.middles[idx].append(self.rightLine[idx])
            ret.append(list(self.middles[idx]))
        return ret
    def splitLine(self, matrix):
        leftLine=deque()
        rightLine=deque()
        middles = deque()
        for row in range(len(matrix)):
            leftLine.append(matrix[row][0])
            rightLine.append(matrix[row][-1])
            middles.append(deque(matrix[row][1:-1]))
        return leftLine,rightLine,middles

def solution(rc, operations):
    matrix = Matrix(rc)
    for o in operations:
        if o == 'ShiftRow':
            matrix.shiftRow()
        else:
            matrix.rotate()
    return matrix.getMatrix()