시간초과와 메모리초과가 까다로웠던 문제

백준 9019-DSLR

첫 접근- BFS, 시간초과로 실패

문제에서 정의된 D,S,L,R 함수를 거치면서 생성되는 새로운 수와 이제까지 거쳐온 경로 문자열을 큐 배열에 담아 순회하며 목표숫자를 탐색하는 로직을 구현했다. 그렇지만 시간초과를 받았다.

const input = require('fs')
  .readFileSync(process.platform == 'linux' ? 'dev/stdin' : 'test/test.txt')
  .toString()
  .trim()
  .split('\n')
const REGISTER_CAPACITY = 10000
const TESTS = +input[0]
const tests = input.slice(1).map((l) => l.split(' ').map(Number))

class DSLR {
  constructor() {}
  static executeD(register) {
    return register * 2 > 9999 ? (register * 2) % 10000 : register * 2
  }
  static executeS(register) {
    return (register + 9999) % 10000
  }
  static executeL(register) {
    return ((register * 10) % 10000) + Math.floor(register / 1000)
  }
  static executeR(register) {
    return (register % 10) * 1000 + Math.floor(register / 10)
  }
}

const solution = (startNum, endNum) => {
  const queue = [[startNum, '']]
  while (queue) {
    const [num, history] = queue.shift()
    if (num === endNum) return history
    const command = ['D', 'S', 'L', 'R']
    for (let i = 0; i < 4; i++) {
      const nextNum = DSLR[`execute${command[i]}`](num)
      queue.push([nextNum, history + command[i]])
    }
  }
}

const answer = tests
  .reduce((acc, curr) => {
    acc.push(solution(...curr))
    return acc
  }, [])
  .join('\n')

console.log(answer)

두 번째 시도 - 메모이제이션을 활용한 최적화 - 실패

방문했던 노드(숫자)를 큐에서 다시 pop하는 경우가 존재할 것이다. 최대 네 자리수이기에, 그 중복은 더욱 심할 것이라 판단하여 visited 배열을 별도로 선언하여 특정 숫자의 등장 여부를 체크하는 로직을 추가하였다.
하지만 실패하였다.

const readline = require('readline')
const fs = require('fs')

const rl = readline.createInterface({
  input: process.platform === 'linux' ? process.stdin : fs.createReadStream('test/test.txt'),
  output: process.stdout,
})
const REGISTER_CAPACITY = 10000
class DSLR {
  constructor() {}
  static executeD(register) {
    return register * 2 > 9999 ? (register * 2) % 10000 : register * 2
  }
  static executeS(register) {
    return register === 0 ? 9999 : register - 1
  }
  static executeL(register) {
    return ((register * 10) % REGISTER_CAPACITY) + Math.floor(register / 1000)
  }
  static executeR(register) {
    return (register % 10) * 1000 + Math.floor(register / 10)
  }
}

const command = ['D', 'S', 'L', 'R']
const bfs = (startNum, endNum) => {
  const visited = Array.from({ length: REGISTER_CAPACITY + 1 }, () => '')
  const queue = [[startNum, '']]
  while (queue.length) {
    const [dequeued, historyStr] = queue.shift()
    if (dequeued === endNum) {
      break
    }
    for (let i = 0; i < 4; i++) {
      const nextNum = DSLR[`execute${command[i]}`](dequeued)
      const nextHistoryStr = historyStr + command[i]
      if (visited[nextNum]) continue
      visited[nextNum] = historyStr
      queue.push([nextNum, nextHistoryStr])
    }
  }
  return visited[endNum]
}

let idx = 0
const answer = []
rl.on('line', (l) => {
  if (idx++ > 0) {
    const testRes = bfs(...l.split(' ').map(Number))
    answer.push(testRes)
  }
})

rl.on('close', () => {
  console.log(answer.join('\n'))
})

3차 시도 - 메모리초과

input을 readline에서 fs모듈로 변경하고 실행한 코드에서는 메모리 초과가 발생하였다. 나는 왜 메모리 초과가 발생하는지 전혀 이해를 하지 못하고 있었다.

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

class DSLR {
  constructor() {}
  static executeD(register) {
    return register * 2 > 9999 ? (register * 2) % 10000 : register * 2
  }
  static executeS(register) {
    return (register + 9999) % 10000
  }
  static executeL(register) {
    return ((register * 10) % 10000) + Math.floor(register / 1000)
  }
  static executeR(register) {
    return (register % 10) * 1000 + Math.floor(register / 10)
  }
}

const answer = []

input.slice(1).forEach((l) => {
  const [startNum, endNum] = l.split(' ').map(Number)
  const queue = [[startNum, '']]
  const visited = Array(10000).fill(0)
  visited[startNum] = 1
  let head = 0
  while (queue.length > head) {
    const [num, history] = queue[head++]
    visited[num] = 1
    if (num === endNum) {
      answer.push(history)
      break
    }
    const command = ['D', 'S', 'L', 'R']
    for (let i = 0; i < 4; i++) {
      const nextNum = DSLR[`execute${command[i]}`](num)
      if (!visited[nextNum]) queue.push([nextNum, history + command[i]])
    }
  }
})

console.log(answer.join('\n'))

4차 시도 - 통과 코드와 시간초과 코드의 차이? - 함수 대신 정적메서드를 사용하면 더 느리다.

마침내 문제 풀이에 성공했다. 내 코드가 메모리초과가 발생했던 이유는 큐에 push하기 전에 방문처리를 하지 않아서였다.

원칙적으로 BFS에서는 큐에서 dequeue한 노드에 대해 방문처리를 진행해주어야 한다. 하지만 이렇게 되면 큐에 동일한 노드가 enqueue되는 것을 방지할 수가 없다. 그래서 각 커맨드를 순회하며 새로운 숫자를 만드는 for문에서 방문 처리를 해주었다.

또한, 정적메서드 사용 대신 일반 함수를 정의하여 사용하는 것이 속도가 더욱 빠르게 나오는 듯하다. 같은 로직이지만 클래스 정적메서드로 구현했을 때는 시간초과가 나왔다.

//통과코드
const input = require('fs')
  .readFileSync(process.platform == 'linux' ? 'dev/stdin' : 'test/test.txt')
  .toString()
  .trim()
  .split('\n')

function executeD(register) {
  return register * 2 > 9999 ? (register * 2) % 10000 : register * 2
}
function executeS(register) {
  return (register + 9999) % 10000
}
function executeL(register) {
  return ((register * 10) % 10000) + Math.floor(register / 1000)
}
function executeR(register) {
  return (register % 10) * 1000 + Math.floor(register / 10)
}

const DSLR = [executeD, executeS, executeL, executeR]

const answer = []

input.slice(1).forEach((l) => {
  const [startNum, endNum] = l.split(' ').map(Number)
  const queue = [[startNum, '']]
  const visited = Array(10000).fill(0)
  visited[startNum] = 1
  let head = 0
  while (queue.length > head) {
    const [num, history] = queue[head++]
    visited[num] = 1
    if (num === endNum) {
      answer.push(history)
      break
    }
    const command = ['D', 'S', 'L', 'R']
    for (let i = 0; i < 4; i++) {
      const nextNum = DSLR[i](num)
      if (0 <= nextNum && nextNum < 10000 && !visited[nextNum]) {
        queue.push([nextNum, history + command[i]])
        visited[nextNum] = 1
      }
    }
  }
})

console.log(answer.join('\n'))

//시간초과 코드
const input = require('fs')
  .readFileSync(process.platform == 'linux' ? 'dev/stdin' : 'test/test.txt')
  .toString()
  .trim()
  .split('\n')

class DSLR {
  constructor() {}
  static executeD(register) {
    return register * 2 > 9999 ? (register * 2) % 10000 : register * 2
  }
  static executeS(register) {
    return (register + 9999) % 10000
  }
  static executeL(register) {
    return ((register * 10) % 10000) + Math.floor(register / 1000)
  }
  static executeR(register) {
    return (register % 10) * 1000 + Math.floor(register / 10)
  }
}

const answer = []

input.slice(1).forEach((l) => {
  const [startNum, endNum] = l.split(' ').map(Number)
  const queue = [[startNum, '']]
  const visited = Array(10000).fill(0)
  visited[startNum] = 1
  let head = 0
  while (queue.length > head) {
    const [num, history] = queue[head++]
    visited[num] = 1
    if (num === endNum) {
      answer.push(history)
      break
    }
    const command = ['D', 'S', 'L', 'R']
    for (let i = 0; i < 4; i++) {
      const nextNum = DSLR[`execute${command[i]}`](num)
      if (0 <= nextNum && nextNum < 10000 && !visited[nextNum]) {
        queue.push([nextNum, history + command[i]])
        visited[nextNum] = 1
      }
    }
  }
})

console.log(answer.join('\n'))