표 편집

Cramming An·2022년 5월 3일
0

Code Interview

목록 보기
3/11
post-thumbnail

문제 접근

이 문제는 문제에 제시된 시뮬레이션을 그대로 구현하면 되는 문제이다.

우선 문제에 제시된 데이터들을 보자

  • 선택된 행 (인덱스)
  • 구별된 값을 가진 표
// index 0,1,2,3
const arr = [1,2,3,4] // 각 데이터들을 구분해야하는 이유는 최종적으로 특정 데이터가 남아있는지, 아닌지 판단해야하기 때문
  • 삭제 기록 스택
  • 특정 데이터가 있는지 없는지 추적하는 해시맵

시간복잡도 문제

사실 이 문제에 많은 시간을 썼지만 결국 시간복잡도의 문제는 풀지 못했다.
그 이유는 다음과 같다.

  1. 기본적으로 cmd의 모든 명령어를 전부 탐색해야한다. (200,000)
  2. 만약 표 데이터를 배열에 저장하면 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을 좀 더 적극적으로 사용해야겠다.

profile
La Dolce Vita🥂

0개의 댓글