백준10866 - 덱 (연결리스트) JS

https://www.acmicpc.net/problem/10866

해당 문제는 배열로 풀이하는 것으로 접근했다가 시간 초과 문제가 발생했다.

입력값으로 들어오는 최대 명령 수가 1만 이하다보니, shift 메서드의 높은 시간복잡도 때문이었을 것이다.

 

그래서 class 객체를 사용해 연결 리스트를 구현하는 방법에 대해 찾아보았다.

참고한 링크 https://lhoiktiv.tistory.com/204?category=887263 

 

const fs = require('fs')
const input = fs.readFileSync(process.platform === "linux" ? "/dev/stdin":"입력.txt")
  .toString().trim().split('\n')

// 연결리스트를 이루는 Node
// 첫 | 마지막 노드 삭제 시 삭제된 노드의 값을 기록하기 위해
// prev | next라는 요소를 갖게 구현
class Node {
  constructor(value) {
    this.value = value
    this.prev = null
    this.next = null
  }
}

class Deck {

  constructor() {
    // 위와 같은 이유로 첫 노드와 마지막 노드 기록하기 위한 head | tail
    this.head = null
    this.tail = null
    this.length = 0
  }
  
  // 맨앞 노드 추가
  push_front(value) {
    const node = new Node(value)

    if(!this.length) {
      // Deck이 비어있을 경우, 
      // 삽입되는 노드는 온전히 본인 뿐이기에 head와 tail을 모두 차지하게 됨
      this.head = node
      this.tail = node
    } else {
      // Deck이 비어있지 않을 경우,
      // 기존 Deck의 맨앞에 위치한 노드의 prev는 추가된 'node'
      this.head.prev = node
      // 추가된 'node'의 다음 노드는 기존에 맨앞에 위치했던 노드
      node.next = this.head
      // Deck의 head는 추가된 'node'로 수정
      this.head = node
    }
    this.length ++
  }

  // 맨앞 노드 삭제 및 반환
  pop_front() {
    // 비어있을 경우 -1 반환 (문제에서 요구)
    if(!this.length) return -1
    
    const shift = this.head
    // Deck의 head는, 맨앞에 있던 노드의 next(다음값)로 수정
    this.head = this.head.next
    // Deck 요소가 하나만 있을 경우, 덱이 비게 될 것이므로 => head = null
    
    // Deck 요소가 여럿일 경우, 
    // this.head = this.head.next 로 위에서 선언해두었으므로 
    // this.head 가 가지고 있던 prev(맨 앞이었던 노드)를 null로 초기화
    this.length === 1 ? this.head = null : this.head.prev = null
    this.length --
    return shift.value
  }
  
  // 맨뒤 노드 추가
  // push_front 메서드와 원리는 비슷하므로 설명 생략
  push_back(value) {
    const node = new Node(value)
    if(!this.length) {
      this.head = node
      this.tail = node
    } else {
      this.tail.next = node
      node.prev = this.tail
      this.tail = node
    }
    this.length ++
  }
  
  // pop_front 메서드와 원리는 비슷하므로 설명 생략
  pop_back() {
    if(!this.length) return -1    
    const pop = this.tail
    this.tail = this.tail.prev
    this.length === 1 ? this.tail = null : this.tail.next = null
    this.length --
    return pop.value
  }

  size () {
    return this.length
  }

  empty () {
    return this.length ? 0 : 1
  }

  front () {
    return !this.length ? -1 : this.head.value
  }

  back () {
    return !this.length ? -1 : this.tail.value
  }
}

function solution(data) {
  data.shift()

  const deck = new Deck()
  const result = []

  data.forEach((el)=> {
    const [cmd, num] = el.split(' ')
    result.push(deck[cmd](num))
  })
  
  // 'Deck'의 리턴값을 담아놓은 result 배열에
  // 반환되지 않은 값을 isNaN을 통해 필터링하여 출력
  console.log(result.filter(v => !isNaN(v)).join('\n'))
}

solution(input)