백준 10871번

백준 10871번을 반복문을 사용하여 풀어보았다.

let input = require('fs').readFileSync('/dev/stdin').toString().split('\n')

const N = Number(input[0].split(' ')[0])
const X = Number(input[0].split(' ')[1])

let output = ''

for (let i = 0; i < N; i++) {
  const number = input[1].split(' ').map(Number)[i]
  if (number < X) output += `${number} `
}

console.log(output.trim())

 

정답은 올바르게 출력해내지만 시간 초과가 떴다.

 

그래서 메소드를 사용하여 풀어봤고, 다행히 통과했다.

let input = require('fs').readFileSync('/dev/stdin').toString().split('\n')

input[1].split(' ')
  .filter((value) => value < X)
  .forEach((value) => output += `${value} `)

console.log(output.trim())

 

결과적으로는 메소드를 사용한 풀이로 통과하긴 했지만

 

마냥 무난해보이는 첫번째 코드에서 도대체 뭐가 문제였던건지 감이 안 잡히기도 했고

 

시간 초과가 뜬 적은 처음이라 그 이유를 짚고 넘어가고 싶었다.

 

그래서 알아보니 두 가지가 의심이 되었다.

 

1. output  += `${number} `로 문자열을 반복적으로 이어붙인 것

 

JavaScript에서 모든 기본형은 불변값으로, 값이 한 번 정해지면 변경할 수 없다.

 

그럼에도 값을 변경한다면 기존 메모리 주소에 저장된 값이 변경되는 것이 아니라 다른 메모리 주소에 변경된 값이 새롭게 저장된다.*

 

즉, output += `${number} `로 output의 값을 변경할 때마다 다른 메모리 주소에 변경된 값이 새롭게 저장되므로

 

소요되는 메모리와 시간이 증가하는 것이다.

 

이를 대체하기 위해 객체 자료형인 배열을 사용할 수 있다.

let input = require('fs').readFileSync('/dev/stdin').toString().split('\n')

const N = Number(input[0].split(' ')[0])
const X = Number(input[0].split(' ')[1])

let output = []

for (let i = 0; i < N; i++) {
  const number = input[1].split(' ').map(Number)[i]
  if (number < X) output.push(number)
}

console.log(output.join(' '))

 

그러나 이 풀이로도 시간 초과가 발생했고, output += `${number} `가 문제가 아닌 것 같았다.

 

2. input[1].split(' ')으로 split을 반복적으로 사용한 것

 

split은 배열을 반환하고, 때문에 호출될 때마다 배열을 생성하기 위한 시간이 소요된다.

 

이러한 이유로 split을 반복적으로 사용할 경우 소요되는 시간이 증가할 수 있다.

 

이를 해결하기 위해 split을 반복문 외부로 이동시켰다.

let input = require('fs').readFileSync('/dev/stdin').toString().split('\n')

const N = Number(input[0].split(' ')[0])
const X = Number(input[0].split(' ')[1])
const numbers = input[1].split(' ').map(Number)

let output = ''

for (let i = 0; i < N; i++) {
  if (numbers[i] < X) output += `${numbers[i]} `
}

console.log(output.trim())

 

이렇게 하니 다행히 시간 초과 없이 통과할 수 있었다.

 

* 참고) JavaScript의 불변 객체

 

💫 이 문제를 통해 배운 것

반복문 내부에서 split 메소드를 사용하는 것은 시간 소요를 크게 증가시킬 수 있으니 지양하자.