이 문제는 정확성과 효율성이 존재했다. 정확성을 다 맞춘다는 생각으로 구현하면 그냥 배열 회전, inqueue, dequeue만 하면 되기 때문에 우선 정확성을 맞추기 위해 아래 코드를 작성했다.
function solution(rc, operations) {
for (const op of operations) {
if (op === "ShiftRow") {
shift()
} else {
rotate()
}
}
function shift() {
rc.unshift(rc.pop())
}
function rotate() {
const temp = rc[0][0]
for (let i = 1; i < rc.length; i++) {
rc[i-1][0] = rc[i][0]
}
for (let i = 1; i < rc[0].length; i++) {
rc[rc.length - 1][i - 1] = rc[rc.length - 1][i]
}
for (let i = rc.length - 1; i > 0; i--) {
rc[i][rc[0].length - 1] = rc[i - 1][rc[0].length - 1]
}
for (let i = rc[0].length - 1; i > 1; i--) {
rc[0][i] = rc[0][i - 1]
}
rc[0][1] = temp
}
return rc
}
여기서 어떤 부분을 최적화할 수 있을까? operation이 지금 100000개니까 만약 모두 rotate 연산이라면 바깥 테두리수의 개수를 X라 하면 X * 100000의 시간 복잡도를 갖는다. 이 때 X의 범위는 200000이 될 수 있다.(문제의 조건에 따라) 그렇다면 연산의 개수가 너무 많아지게 된다.
따라서 나는 rotate를 최적화 해보기로 했다. shiftRow는 그대로 반영하면 되지만 연속된 rotate는 한번의 연산으로 최적화할 여지가 있다. 한 바퀴 돌리는 경우 rotate는 무의미하다. 따라서 나는 아래와 같은 코드를 작성했다.
function solution(rc, operations) {
const blockCount = calculateBlockCount()
while (operations.length) {
let rotateCount = 0
while (true) {
const curr = operations.shift()
if (!curr) {
flushRotate(rotateCount)
break
}
if (curr === "ShiftRow") {
flushRotate(rotateCount)
shift()
break
} else {
rotateCount++
}
}
}
// console.log(rc)
return rc
function flushRotate(rotateCount) {
rotateCount %= blockCount
const top = rc[0].slice(1, -1),
left = [],
right = [],
bottom = rc[rc.length - 1].slice(1, -1)
for (let i = 0; i < rc.length; i++) {
left.push(rc[i][0])
}
for (let i = 0; i < rc.length; i++) {
right.push(rc[i][rc[0].length - 1])
}
for (let i = 0; i < rotateCount; i++) {
right.unshift(top.pop())
bottom.push(right.pop())
left.push(bottom.shift())
top.unshift(left.shift())
}
for (let i = 1; i < rc[0].length - 1; i++) {
rc[0][i] = top[i - 1]
}
for (let i = 0; i < rc.length; i++) {
rc[i][0] = left[i]
}
for (let i = 0; i < rc.length; i++) {
rc[i][rc[0].length - 1] = right[i]
}
for (let i = 1; i < rc[0].length - 1; i++) {
rc[rc.length - 1][i] = bottom[i - 1]
}
}
function shift() {
rc.unshift(rc.pop())
}
function calculateBlockCount() {
const n = rc.length
const m = rc[0].length
return n * 2 + m * 2 - 4
}
}
근데 조금만 더 생각해보면 몇 바퀴 돌리는지는 그렇게 큰 의미가 없다. 왜냐면 시간복잡도에서 상수항이기 때문이다. 중요한 것은 지금 배열을 조작하는데 테두리의 개수만큼의 시간복잡도 O(nm)를 100000번 수행할 가능성이 있고 위의 최적화는 시간복잡도에 별다른 의미를 주지 못한다는 것을 깨달았다. 그렇다면 테두리의 개수만큼 배열을 조작하는 mutation 자체를 최적화해야하는데 어떤 방법으로 할 수 있을까? 배열의 pop, push 연산은 O(1) 시간복잡도를 갖는다. 배열을 계속 수정하는 것이 아니라 pop, push, shift 같은 메서드를 적극 활용해서 배열을 회전시켜야 한다.
function solution(rc, operations) {
const rows = rc.map((row) => row.slice(1, -1))
const left = rc.map((row) => row[0])
const right = rc.map((row) => row[row.length - 1])
function shift() {
left.unshift(left.pop())
rows.unshift(rows.pop())
right.unshift(right.pop())
}
function rotate() {
rows[0].unshift(left.shift())
right.unshift(rows[0].pop())
rows[rows.length - 1].push(right.pop())
left.push(rows[rows.length - 1].shift())
}
for (const curr of operations) {
if (curr === "ShiftRow") {
shift()
} else {
rotate()
}
}
return rows.map((row, i) => {
return [left[i], ...row, right[i]]
})
}
배열을 왼쪽부분, 오른쪽 부분, 가운데 부분으로 나누고 회전시키는 로직을 위와 같이 작성했다. 여기서 또 문제가 발생한다. JavaScript에서 unshift()의 시간 복잡도는 O(N)이다. 배열이니까 뒤로 모든 요소를 이동시키는데 O(N)의 시간 복잡도를 가지기 때문이다. 이를 개선하려면 어떻게 해야할까? 자료구조를 직접 만들어서 해결할 수 있다. Deque을 직접 만들고 LinkedList 처럼 연결하면 삽입 연산을 O(1)에 해결할 수 있기 때문에 문제를 풀 수 있다.