[2022 KAKAO TECH INTERNSHIP] Q5. 행렬과 연산 (C++, Python, Java)

문제 링크

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

 

예상 난이도

P5

 

알고리즘 분류

덱, 구현

 

풀이

아마 5번 문제를 건드릴 정도면 시간복잡도에 대해서는 충분히 이해를 하고 있을거라고 생각합니다. 주어진 연산을 곧이곧대로 짜면 당연히 시간초과가 나고, 시간복잡도를 짐작할 때 극단적인 케이스인 2 × 50000, 50000 × 2와 같은 배열 또한 당연히 고려를 해야합니다. 그리고 문제의 난이도는 많이 차이가 나지만 BOJ 5430과 같은 예시를 통해 문제에서 요구하는 연산을 영리하게 처리할 수 있어야 한다는 것을 알 수 있습니다.

 

예를 들어 BOJ 5430에서는 Reverse를 처리할 때 배열을 직접 뒤집는 대신 뒤집혔는지 여부를 저장하는 변수를 두어 O(1)에 처리합니다.

 

우선 ShiftRow는 직접 행렬을 바꾸는 대신 그냥 최상단에 위치한 행이 몇 번째 행인지만 알면 되기 때문에 O(1)에 처리가 가능합니다.

 

실제 ShiftRow를 적용한 예시입니다.

 

그런데 문제는 Rotate입니다. 총 2R+2C-2개의 원소를 이동시켜야 하고, 각 행을 deque로 생각하면 1행과 R행에서의 연산은 O(1)으로 처리할 수 있지만 결국 모든 행의 값을 건드려야 하고 각 행에서 앞/뒤의 원소를 서로 주고 받기 때문에 어떻게 해결해야 할지 감이 전혀 안옵니다. 참고로 저는 여기서 막혀서 덱을 이용하는 대신 배열의 인덱스를 잘 조작하는 방식을 써서 O(RC × min(R,C))라는 요상한 시간복잡도로 해결을 했습니다. 이렇게 짜면 R이 C 이상일 때, C가 R 이상일 때 각각의 경우를 나눠서 구현을 해야하고 구현 난이도도 상당히 높습니다. 인덱스를 조작해서 푸는 방법은 설명을 별도로 드리지 않을거지만 인덱스가지고 장난치는 능력을 길러보고 싶다면 이렇게 한 번 짜보는 것도 나쁘지 않을지도...?

 

 이 문제를 덱으로 풀기 위해서는 1열과 C열을 별도로 분리한다는 아이디어를 떠올려야 합니다. 이 아이디어를 떠올리고 나면 Rotate가 1열/C열/1행/R행 이 4개의 덱의 앞뒤에서 원소를 주고 받는 연산임을 알 수 있습니다. front, back을 어디로 잡을지는 구현하는 사람 마음이지만 저는 그림에서 표시한 것 처럼 잡았습니다.

 

이렇게 1열과 C열을 분리한 상황에서 ShiftRow과 Rotate를 다시 살펴보면 ShiftRow에서는 idx를 1 감소시키고 또 1열과 C열을 회전시킵니다. Rotate에서는 1열/C열/idx번째 행(이게 최상단에 있는 행)/idx-1번째 행(이게 최하단에 있는 행)에 대해 적절하게 push, pop을 하면 됩니다.

 

실제 예시를 보겠습니다. 오른쪽에는 실제 배열을 두고 왼쪽에서는 코드로 가지고 있을 정보를 두었습니다.

 

ShiftRow를 적용하면 1열, C열을 회전하고 idx를 1 빼서 3으로 보냅니다.

 

그 후 Rotate를 적용하면 1열, C열, 3행, 2행끼리 정보를 잘 주고 받습니다. 굉장히 난장판이지만 4페이지 위에 있는 그림에서 행만 1행, R행에서 3행, 2행으로 바뀌었다고 이해하시면 됩니다.

 

다음으로 ShiftRow를 2번 적용하고

 

Rotate도 적용했습니다. 연산을 다 적용한 후에는 각 deque의 값을 가지고 원래 배열을 복원하면 됩니다.

 

 

한편 ShiftRow를 처리할 때 idx 변수를 두는 대신 행들을 모은 새로운 deque(즉 deque의 deque)을 두어 그 deque을 회전시키는 방법도 있습니다.

 

하지만 C++에서는 그냥 늘 짜던대로 짜면 deque 전체에 대한 복사가 이루어져서 O(1)이 아니라 O(C)에 동작해 시간 초과가 발생합니다. 이걸 회피하려면 rows를 deque<deque<int> *>로 두거나 move와 emplace_back을 이용해 row 전체에 대한 복사가 발생하지 않도록 해야하는데 포인터는 뭔가 마음에 안들고 move와 emplace_back을 이용하는건 생성자/소멸자/rvalue 등과 같은 C++에 대한 약간의 깊은 이해를 필요로 하기 때문에 그냥 마음 편하게 idx를 쓰는게 낫지 않나 싶긴 합니다. 사실 저도 처음엔 포인터를 생각했지 move와 emplace_back을 이용한 방법은 몰랐는데 풀고 나서 다른 사람의 코드를 보다가 알게 된 문법이었습니다.

 

코드(C++)

4개의 덱에서 값을 주고받을 때 순서를 잘 설정하면 C = 2 여서 row가 empty일 때에 대한 예외처리를 안해도 됩니다.

 

코드(Python)

Python의 deque에서 인덱스로 값 접근은 길이가 n일 때 O(1)이 아닌 O(n/64)입니다. 그렇기 때문에 인덱스로 값을 접근하지 않는 것이 좋습니다. 예를 들어 24-28번째 줄에서 매번 pop을 하는 대신 ret[i][0] = col1[i] / ret[i][j] = row[(i+idx)%r][j-1] 등과 같이 처리하면 바람직하지 않습니다. 이 문제의 상황에서는 R, C가 최대 5만으로 작아 시간에 큰 차이가 없지만 deque의 크기가 커진다면 큰 차이를 불러올 수 있습니다. 

 

코드(Java)