이 문제는 문제에 제시된 시뮬레이션을 그대로 구현하면 되는 문제이다.
우선 문제에 제시된 데이터들을 보자
// index 0,1,2,3
const arr = [1,2,3,4] // 각 데이터들을 구분해야하는 이유는 최종적으로 특정 데이터가 남아있는지, 아닌지 판단해야하기 때문
사실 이 문제에 많은 시간을 썼지만 결국 시간복잡도의 문제는 풀지 못했다.
그 이유는 다음과 같다.
- 기본적으로
cmd
의 모든 명령어를 전부 탐색해야한다. (200,000
)- 만약 표 데이터를 배열에 저장하면
C
,Z
명령시splice
,pop(n)
을 사용하게 된다..
따라서 시간초과가 발생하고, 이것을 해결할 방법은 표 데이터를 저장할 데이터 구조를 새로 선정한 것 뿐임을 알 수 있다.
이중 연결리스트를 사용하면 C
,Z
명령시 현재 노드의 이전노드과 다음노드에 접근하면 되므로 시간복잡도가 O(1)
입니다.
하지만 JS에서는 자료구조를 생성자 함수로 구현할 필요가 있었습니다.
const MakeNode = function (idx, prev, next) {
this.prev = prev
this.next = next
this.idx = idx
}
const startNode = new MakeNode(0, null, null)
let curNode = startNode
let prevNode = startNode
function solution(n, k, cmd) {
const MakeNode = function (idx, prev, next) {
this.prev = prev
this.next = next
this.idx = idx
}
const startNode = new MakeNode(0, null, null)
let curNode = startNode
let prevNode = startNode
for (let i = 1; i < n; i++) {
const newNode = new MakeNode(i, prevNode, null)
prevNode.next = newNode
prevNode = newNode
if (i === k) curNode = newNode
}
const stackZ = []
const resultObj = new Array(n).fill(0).reduce((acc, curr, idx) => {
acc.set(idx, 'O')
return acc
}, new Map())
cmd.forEach((command) => {
const comArr = command.split(' ')
if (comArr[0] === 'D') {
const num = +comArr[1]
for (let i = 0; i < num; i++) if (curNode.next) curNode = curNode.next
} else if (comArr[0] === 'U') {
const num = +comArr[1]
for (let i = 0; i < num; i++) if (curNode.prev) curNode = curNode.prev
} else if (comArr[0] === 'C') {
stackZ.push(curNode)
resultObj.set(curNode.idx, 'X')
const prevNode = curNode.prev
const nextNode = curNode.next
if (prevNode && nextNode) {
prevNode.next = nextNode
nextNode.prev = prevNode
curNode = nextNode
} else if (prevNode) {
prevNode.next = null
curNode = prevNode
} else if (nextNode) {
nextNode.prev = null
curNode = nextNode
}
} else if (comArr[0] === 'Z') {
const poppedNode = stackZ.pop()
resultObj.set(poppedNode.idx, 'O')
const prevNode = poppedNode.prev
const nextNode = poppedNode.next
if (prevNode) prevNode.next = poppedNode
if (nextNode) nextNode.prev = poppedNode
}
})
const answer = []
resultObj.forEach((value) => answer.push(value))
return answer.join('')
}
코딩테스트 문제에서 이중 연결 리스트를 사용한 것은 처음이어서 꽤 많은 시간을 소비했다.
특히,
resultObj
를 처음에 JS 리터럴 객체로 구현했다. 하지만 value
값을 배열로 뽑아낼 때 시간 초과가 난 적이 있다.Object.entries(resultObj).
n < 1,000,000
이어서 괜찮을 줄 알았지만 아니었다.
앞으로는 Map
을 좀 더 적극적으로 사용해야겠다.