---
layout: post
title: "자잘한 도움말 #6 백준 10845번 (큐) NodeJS로 풀기"
description: 백준 10845번, 백준 큐 NodeJS, Node 콘솔 출력 속도
date: 2022-07-28 20:34:00 +0900
categories: [Micro]
---

## TL;DR

- [큐](https://www.acmicpc.net/problem/10845), [큐 2](https://www.acmicpc.net/problem/18258)
- 콘솔 출력이 잡아먹는 시간이 크기 때문에 출력이 많이 발생하는 문제에선  
  결과를 **버퍼 배열에 담아 한번에 출력**하자.

```javascript
const buffer = [];
// ...
buffer.push(/* some output */);
// ...
console.log(buffer.join("\n"));
```

## 이하 그리 중요하진 않은 내용들

![아](https://i.postimg.cc/MTFcpL61/image.jpg)
{: .center}

이번 주제가 자료구조에 국한된 것은 아닌데, 자료구조 하니까 옛날 일이 생각난다. 살다보면 자려고 누웠을 때 갑자기 내 머릿 속에서부터 두개골을 빡 때리면서 덮고 있던 이불을 차게 만드는 순간이 몇 번 씩 생기곤 한다. 나는 그 중 하나가 **자료구조를 경시하던 시절**이다. 그때 내 어록 중 하나가 이랬다:

> 자료구조는 계속 하면 뭐가 더 있어요?

이 바보같은 녀석... 최근엔 [CRDT](https://en.wikipedia.org/wiki/Conflict-free_replicated_data_type)니 뭐니 하는 요상한 이름들을 접하면서 이불을 차는 힘이 더 세졌다. [큐](https://www.acmicpc.net/problem/10845) 문제가 시간 초과를 내뱉었을 때도 저랬던 시절이 떠올랐었지.

### 백준 10845번, 큐

[백준의 10845번 문제, 큐](https://www.acmicpc.net/problem/10845)는 [solved.ac](https://solved.ac) 기준 난이도 실버 4의 아주 쉬운 문제다. 롤에서도 차마 입 밖으로 내뱉기 힘든 그 계급, 실버 4는 아주 쉽다는 의미고, 이 문제에서 시간 초과가 나왔을 때 내 기분은 마치

![어?](https://i.postimg.cc/0QjDW6cb/image.jpg)  
{: .center}

이... 이게 왜 안풀리지...?

아무튼 이 때가 2021년 1월 경이었고, 대학교를 졸업한 이후 마음이 붕 떠있던 중이라 문제를 풀겠다는 의지가 많이 부족한 시기였다. 그래서 그냥 Node의 문제구나.. 하고 넘어갔었다. 큐와 그 구현 방법에 대한걸 모르는건 아니니까. (이거 사실 따라하면 안되는 상당히 나쁜 습관이다.)

그렇게 다사다난한 1년을 보낸 후 지금으로부터 약 6개월 전, 2022년 1월 경에 [큐 2](https://www.acmicpc.net/problem/18258)라는 문제를 마주하게 되었다. 그리고 똑같이 시간초과의 늪에 빠지게 되었다. 생각해보니 개발을 그렇게 해놓고도 아직도 못풀고 있었다는게 엄청 민망한 일이긴 하네.

![분투의 흔적](https://i.postimg.cc/x1THgfnk/image.png)  
근데 "맞았습니다"가 왜 회색이지
{: .center}

다행인건 이 땐 의지가 좀 더 강했다는 것이다. 아무튼 오늘은 저 흔적을 따라가보자.

### 범인찾기

아무래도 가장 직관적인 추측은 시간복잡도 관련이겠지. 첫 번째 가설은 이랬다.

> O(1)이 나와야 되는데 O(n)이 나온다.

큐를 구현할 때 마주치기 쉬운 아주 전형적인 케이스다. 특히 node가 C/C++ 처럼 빠른 이미지는 아니기도 하고, 그리고 나는 꾸준히 node를 사용해 알고리즘을 풀다보니 자연스레 자바스크립트의 `shift()` 메소드에 손이 갔는데, 좋은 선택이 아니었다. 자바스크립트의 배열 관련 빌트인 메소드는 다음과 같은 시간 복잡도를 가지기 때문.

- `push` : O(1)
- `pop` : O(1)
- `shift` : O(N)

복잡한 이유가 있는 것은 아니고, "배열"에 대한 빌트인 메소드니까 당연한 사실이다. 배열의 첫 번째 요소를 삭제하면 뒤의 요소의 주소까지 모두 영항을 줄 수 밖에 없으니. 그래서 `shift()`를 사용하지 않도록 배열에 인덱스를 두는 방식으로 코드를 수정했고, **나는 다시 시간초과를 받았다.**

![이마](https://i.postimg.cc/KcDGjJ5D/image.gif)
{: .center}

사실, 10845번 큐 문제는 O(N) 시간복잡도로 풀어도 해결할 수 있는 조건을 가지고 있다. 테스트 케이스의 수가 그리 크지 않다. O(N)은 18258번 큐 2 문제에서 고민해야할 사항이었다.

그렇다면 두 번째 가설.

> 알고리즘엔 문제가 없다.

작년 프로젝트를 진행하면서 경험한 것이 있는데, node의 콘솔 출력은 가끔씩 터지기도 한다는 것이다. 아주 많은 데이터를 다루는 프로젝트였는데, 특정 조건에서 코드의 로직상 오류가 없는데도 node 프로세스가 운명을 달리하는 것을 수차례 경험하였다. 그 때의 경험 또한 나중에 정리해 글로 작성하려고 하는데, 아무튼 결과만 말하자면 출력 버퍼가 터진 것이었다. 그리고 이 문제에 그 때의 경험을 확장해 보았다. 어떤 이유에서든 node의 콘솔 출력은 특이하고, 그게 퍼포먼스에도 영향을 준다면?

일단 내가 아는 수준의 지식에서 문제를 해결해보려고 시도했다. `console.log()`는 사실 내부적으로 이러한 코드를 포함한다. `process.stdout.write()`, 프로세스가 가지고 있는 표준 출력 버퍼에 직접 문자열을 입력하는 것이다. 좀 더 저수준의 느낌이 난다. 그리고 나는 모든 `console.log()`를 해당 코드로 바꿔봤다. `console.log`가 고수준으로 추상화된 인터페이스라면 그 과정에서 약간이나마 성능의 손실이 발생하지 않았을까 하는 생각으로.

![물론](https://i.postimg.cc/7YHqmrqd/image.png)
{: .center}

물론 이걸로 해결되진 않았다. 대신 방향성은 맞았다.

### 진범

우선, [`console.log()`가 느린 것은 사실이다.](https://github.com/nodejs/node/issues/10619) 그렇다면 왜? 이 이슈에 달린 mcollina의 답변을 읽어보자.

> The problem you are facing is related to the fact that Node.js is an asynchronous platform. `console.log` does not write strings synchronously to the output, but rather it queue them and deliver through the event loop. Because of this, calling `console.log` in this way would just queue a lot of data to be written, and it will write them when the process ends.
>
> 당신이 겪은 문제는 Node.js가 비동기 플랫폼이기 때문에 발생합니다. `console.log`는 문자열을 출력에 동기적으로 작성하지 않고, 대기열에 넣은 다음 이벤트 루프를 통해 전달합니다. 따라서 `console.log`을 이렇게 호출하는 것은 그저 출력될 많은 데이터를 대기시키는 것에 불과하고, 데이터들은 프로세스가 끝날 때에 출력될 것입니다.

Node의 콘솔 출력이 다른 이유가 이 점에서 나오는 것이다. 싱글 스레드에서 돌아가는 이벤트 기반의 비동기 자바스크립트 실행 환경. 사실 자바스크립트의 영향력을 업고 node의 인기가 꽤 커졌단 체감을 최근 받고 있는데, **그럼에도 불구하고 node는 특이한 존재**라는 것을 잊으면 안될 것 같다. 아마 많이들 node를 뭐라고 불러야 하는지도 헷갈려 할 것이다. 스스로 실행 환경이라고 소개하고 있고, 위의 답변에서 나온 플랫폼이란 표현 또한 적절해 보인다.

노드의 콘솔 출력은 이벤트 기반으로 동작한다. 작년 내가 프로젝트에서 겪었던 문제도 비슷했다, 이벤트 루프를 통해 출력이 충분히 해소되기 전에 대기열에 너무 많은 출력이 들어와 버퍼가 터진 것이었다. **정확히 기억은 안나지만**{: .small} 그때는 출력의 양이 지나치게 많다는 것이 문제였기 때문에 `process.stdout.write`를 쓰면서 직접 이벤트를 핸들링 해 버퍼가 터지지 않도록 해결할 수 있었는데, 이번엔 출력의 속도가 너무 느리다는 것이 문제기 때문에 단순히 `process.stdout.write`를 사용하는 것만으론 해결할 수 없었다.

```javascript
function consoleOutput() {
  for (let i = 0; i < TESTSIZE; i++) {
    console.log(i);
  }
}

function bufferOutput() {
  const buffer = [];
  for (let i = 0; i < TESTSIZE; i++) {
    buffer.push(i);
  }
  console.log(buffer.join("\n"));
}
```

그리고 그 해결법은 바로, 출력 함수를 호출하는 횟수 자체를 줄이는 것이다. 위의 함수와 같이 연산 결과가 나올 때 마다 호출하는 것이 아니라, 결과를 따로 버퍼에 담고, 그 버퍼 통째로 출력시키는 것이다. 간단히 비유하자면, 운송 비용이 너무 많이 드니까 한 번 운송에 싹다 묶어 보내는 것이다. 물론 메모리 손해는 좀 본다. 위의 코드 제출 스크린샷을 보면 통과한 코드의 메모리 사용량이 엄청나단 것을 볼 수 있다.

![속도](https://i.postimg.cc/Prs7q6sr/image.png)
{: center}

출력을 5만 줄 수행했을 때 이만큼이나 속도 차이가 발생한다.

## 내가 배운 것

[지난번 문제](/micro/2022/05/05/micro-tip-5.html) 처럼 이번 문제도 꽤 오랫동안 담아둔 주제였다. 이번에 글을 쓰면서 다시 한 번 내용을 훑어보니 내가 놓쳤던 부분을 다시금 되새길 수 있었던 것 같다. 그나저나 WSL도 그렇고 Node도 그렇고, 익숙한 듯이 막 쓰고는 있는데 생각보다 그 특성을 까먹고 쓰면서 문제를 겪는 일이 자주 일어나는 것 같다. 내가 자료구조를 경시하다가 큐 문제에 뇌정지가 왔던 것 처럼(애초에 개념이 튼튼했으면 바로 다른 문제점을 찾으려 눈을 돌리지 않았을까?) 그 근본에 있는 지식들을 항상 명심해두며 살아야 할 것 같다.

- 자료구조 무시하지 말자
- Node.JS, 싱글 스레드에서 돌아가는 이벤트 기반의 비동기 자바스크립트 실행 환경
- **기본에 충실해야 더 넓은 시야를 가질 수 있다**
