Swift를 사용해서 행렬과 연산 문제를 풀이합니다.
먼저 문제를 간단하게 요약하면
NxM
행렬이 들어온다.2
가지 방법의 연산이 존재한다.ShiftRow
그리고 두 번째 연산은 Rotate
다.효율적
으로 위에 언급한 두 가지 연산을 해 낼수 있도록 구현한다.가 됩니다.
그리고, 다음으로는 문제의 제약 사항을 볼 필요가 있는데 다음과 같습니다.
rc
의 행 길이(=행렬의 가로 길이) ≤ 50,000rc
의 모든 행의 길이는 동일합니다.rc
의 열 길이(=행렬의 세로 길이) ≤ 50,000rc
의 모든 열의 길이는 동일합니다.rc
의 행 길이 x rc
의 열 길이 ≤ 100,000rc[i][j]
는 i+1
번째 행 j+1
번째 열에 있는 원소를 나타냅니다.rc[i][j]
≤ 1,000,000operations
의 길이 ≤ 100,000operations
의 원소는 "ShiftRow"
혹은 "Rotate"
입니다.여기서 느낄수 있는 것은 제약 사항으로 주어지는 Row, Col의 길이의 단위가 1만 이상의 단위로 꽤나 커질수 있다는 점 입니다.
간단하게 먼저 생각해본 것은, 단순하게 ShiftRow를 어떻게 편하게 할까? 에서 시작을 합니다.
문제에서 주어진 예시를 간단하게 살펴보면
/*
| 1| 2| 3| 4|
| 5| 6| 7| 8|
| 9| 10| 11| 12|
*/
위의 배열같은 그림이 완성이 됩니다.
이 배열에서
row
하나 당 하나의element
로 생각해서 Deque을 만들면 어떨까?
라는 생각을 했는데 그림으로 그려보면 다음과 같습니다.
/*
front
----------------
| 1| 2| 3| 4| - 0번 row
| 5| 6| 7| 8| - 1번 row
| 9| 10| 11| 12| - 2번 row
----------------
rear
*/
대략 위와 같은 그림이 그려지게 되고 실제로 나머지 원소들이 하나의 row
내 에서 Double Linked List
로 이어져있다면, 간단하게 심플한 2중 Deque을 구현 해 낼수 있습니다.
하지만 이 방식은, 순전히
ShiftRow
연산에 대해서만 생각한 것이기 때문에Rotate
에서는 사용 할 수 없습니다.
예를들어, Rotate
연산을 한다 생각하면, 각 행의 양 사이드 들에 의해서 정확하게 Row
의 길이 * 2 만큼의 시간복잡도가 매 연산 마다 일어나게 됩니다.
따라서, 이 방법은 시간 초과를 유발 할 수 있고, 문제에서 요구하는 효율성 테스트를 만족하는 코드가 되지 않을 확률이 높습니다.
Linked List
를 사용한 Deque
을 구현하면 된다 라는 아이디어에서 조금 더 Deque
의 사용 범위를 늘리는 방법을 사용했습니다.
/*
front
----------------
| 1| 2| 3| 4| - 0번 row
| 5| 6| 7| 8| - 1번 row
| 9| 10| 11| 12| - 2번 row
----------------
rear
*/
기존의 방법은 위처럼 단순하게, row
를 큰 Deque
의 원소로 생각을 하게 했는데, 이 부분을 조금 더 확장 시켜서
/*
vfront vfront
| vfront vfront |
| -------- -------- |
| 1| hfront - 2| 3| - hrear 4| - 0번 row
| 5| hfront - 6| 7| - hrear 8| - 1번 row
| 9| hfront - 10| 11| - hrear 12| - 2번 row
| -------- -------- |
| vrear vrear |
vrear vrear
*/
위 그림과 같이 양 사이드를 따로 Veritcal Deque
으로 만들고, 그 내부의 것들은 Horizontal Deque
으로 만들어서 관리하게 만듭니다.(추가적으로 Horizontal Deque
의 front
, rear
들은 서로 위, 아래 방향으로 바라보게 만들었습니다.)
이렇게 될 경우 기존의 ShiftRow
연산에서 생각한 Deque
을 사용한 이득을 거의 그대로 지키는 것과 동시에 Rotate
연산을 사용 할 경우, 단 4번의 넣고 빼는 작업을 통해 빠르게 Rotate를 할 수 있는 장점이 있습니다.
우선 문제를 풀기 위해 사용할 class Code를 보겠습니다.
위의 풀이 방식으로 미루어 보았을 때, 수평으로 양 옆을 바라 보는 경우가 존재하고, 이는 수직 역시 마찬가지입니다.
따라서, 4방향을 모두 쓸 수 있도록(다 쓰지 않더라도 필요하면 쓸 수 있게) 만들 필요가 있었습니다.
저는 간단하게 4방향 모두 뚫어 놓는 방식을 사용했습니다.
코드로 보면
class Node {
var val: Int
var front: Node? = nil
var rear: Node? = nil
var up: Node? = nil
var down: Node? = nil
init() {
val = 0
}
init(_ val: Int, _ front: Node?, _ rear: Node?, _ up: Node?, _ down: Node?) {
self.val = val
self.front = front
self.rear = rear
self.up = up
self.down = down
}
func popH() {
if front != nil { front?.rear = rear }
if rear != nil { rear?.front = front}
}
func popV() {
if up != nil { up?.down = down }
if down != nil { down?.up = up }
}
}
위와 같은 코드로 구현이 되는데, 코드를 보면 알 수 있듯, 4방향(rear
, front
, down
, up
)의 방향을 가지고 있는 class
를 만들어서 쓸 수 있게 됩니다.
특히 popH()
와, popV()
는, 각각 Deque의 양 끝(front
, rear
)에서 바로 앞, 뒤의 원소를 뺄 수 있게끔 해주는 메소드입니다.
정확하게는 해당 원소를 바라보고있는 양 옆의 원소들의 Indicating
방향을 서로에게 겨누게 하는 방식으로 구현이 됩니다!
그리고 저러한 Class
를 문제에 적용하게 되면 다음과 같은 코드가 나오게 됩니다.
import Foundation
class Node {
var val: Int
var front: Node? = nil
var rear: Node? = nil
var up: Node? = nil
var down: Node? = nil
init() {
val = 0
}
init(_ val: Int, _ front: Node?, _ rear: Node?, _ up: Node?, _ down: Node?) {
self.val = val
self.front = front
self.rear = rear
self.up = up
self.down = down
}
func popH() {
if front != nil { front?.rear = rear }
if rear != nil { rear?.front = front}
}
func popV() {
if up != nil { up?.down = down }
if down != nil { down?.up = up }
}
}
var front: [Node] = []
var rear: [Node] = []
var sf: Node = Node(), sr: Node = Node(), ef: Node = Node(), er: Node = Node()
var leftFront = Node(), leftRear = Node(), rightFront = Node(), rightRear = Node()
func initQueues(_ r: Int) {
for i in 0..<r {
front.append(Node())
rear.append(Node())
front[i].rear = rear[i]
rear[i].front = front[i]
}
sf.down = sr
sr.up = sf
ef.down = er
er.up = ef
leftFront.down = leftRear
leftRear.up = leftFront
rightFront.down = rightRear
rightRear.up = rightFront
}
func solution(_ rc:[[Int]], _ operations:[String]) -> [[Int]] {
var answer: [[Int]] = []
initQueues(rc.count)
for i in 0..<rc.count {
for j in 1..<rc[i].count-1 {
let node = Node()
node.val = rc[i][j]
node.front = rear[i].front;
node.rear = rear[i];
rear[i].front?.rear = node;
rear[i].front = node;
}
let n = Node()
n.val = rc[i][0];
n.up = leftRear.up;
n.down = leftRear;
leftRear.up?.down = n;
leftRear.up = n;
let v = Node()
v.val = rc[i][rc[i].count - 1];
v.up = rightRear.up;
v.down = rightRear;
rightRear.up?.down = v;
rightRear.up = v;
}
for i in 0..<rc.count {
front[i].up = sr.up;
front[i].down = sr;
sr.up?.down = front[i];
sr.up = front[i];
rear[i].down = er;
rear[i].up = er.up;
er.up?.down = rear[i];
er.up = rear[i];
}
for i in 0..<operations.count {
if (operations[i] == "ShiftRow") {
let left = sr.up
let right = er.up
sr.up?.popV()
er.up?.popV()
left?.up = sf
left?.down = sf.down
sf.down?.up = left
sf.down = left
right?.up = ef
right?.down = ef.down
ef.down?.up = right
ef.down = right
let ll = leftRear.up
let rr = rightRear.up
leftRear.up?.popV()
rightRear.up?.popV()
ll?.up = leftFront
ll?.down = leftFront.down
leftFront.down?.up = ll
leftFront.down = ll
rr?.up = rightFront
rr?.down = rightFront.down
rightFront.down?.up = rr
rightFront.down = rr
} else {
let left = leftFront.down
leftFront.down?.popV()
left?.front = sf.down
left?.rear = sf.down?.rear
sf.down?.rear?.front = left
sf.down?.rear = left
//
let ru = ef.down?.front
ef.down?.front?.popH()
ru?.up = rightFront
ru?.down = rightFront.down
rightFront.down?.up = ru
rightFront.down = ru
//
let rd = rightRear.up
rightRear.up?.popV()
rd?.front = er.up?.front
rd?.rear = er.up
er.up?.front?.rear = rd;
er.up?.front = rd;
//
let ld = sr.up?.rear
sr.up?.rear?.popH()
ld?.down = leftRear
ld?.up = leftRear.up
leftRear.up?.down = ld
leftRear.up = ld
}
}
var nd = sf.down
let end: Node? = sr
var nf: Node? = ef.down
var left: Node? = leftFront.down
var right = rightFront.down
while nd !== end {
var inp: [Int] = []
var start = nd?.rear
inp.append(left?.val ?? 0)
while start !== nf {
inp.append(start?.val ?? 0)
start = start?.rear
}
inp.append(right?.val ?? 0)
answer.append(inp)
nd = nd?.down
left = left?.down
right = right?.down
nf = nf?.down
}
return answer
}
코드를 보면 꽤나 무시무시한 양의 코드가 나오는데, 처음 풀 때, IDE없이 푸는 상태라 괜히 디버깅이 까다로울 것 같고 생각보다 단순반복 작업이기 때문에 그대로 써도 되겠다 싶어서 전부 다 썼습니다.
실제 코드 양은 꽤 길긴 하지만 그렇게 복잡한 코드는 아닙니다.
여기서 알아가야할 아이디어는 Rotate
연산을 효율적으로 하기 위해 양 사이드를 Deque
으로 감싸서 연산할때 사용한 점과, Swift
에서는 딱히 라이브러리를 통해 Queue
나, Deque
을 지원하고 있지 않은 것 같아서 Swift
유저들은 Linked List
개념을 간단하게 알아가고 적용하는 방법을 배워가면 좋을 것 같습니다.
문제는 그렇게 어렵지 않았습니다!