자바스크립트 코딩테스트 준비 - jabaseukeulibteu kodingteseuteu junbi

처음으로 코딩테스트를 준비하는 분들은 코딩테스트를 위해서 어떤 언어를 선택하는 것이 좋을지 한번쯤은 고민해보셨을 것 같습니다. 전공생이신 분들은 학교에서 적어도 2~3가지의 언어를 접하니, 선택지가 다양해서 더 고민이 됩니다.

일반적으로 코딩테스트를 준비할 때에는 C++이 가장 목적적합하다고 합니다

제가 존경하는 바킹독 형님께서도 C++언어를 추천하고 있습니다. 바킹독 형님께서는 자바나 파이썬은 동작 속도가 느려 전수조사 문제에서 손해를 보고 인터넷 상의 자료도 C/C++에 비해 많이 부족하기 때문에, 자바나 파이썬으로 코딩테스트를 응시하려는 분들께 시간이 많으면 C++로 옮겨타서 코딩테스트를 보는 걸 권하고 있습니다.
(출처: BaaaaaaaarkingDog-[실전 알고리즘] 0x00강 - 오리엔테이션)

그러나 저는 Javascript로 코딩테스트를 준비합니다

코딩테스트를 준비하는 이유, 다르게 말하면 알고리즘을 공부하는 이유는 무엇일까요?
저 같은 취준생에게는 취업의 문턱을 넘기 위해서 일 것입니다. 현업 개발자분께서는 아마도 이직을 위해서 이거나, 개발자로서의 기본 소양을 유지하기 위하여 일 것 같습니다. 또한, 뛰어난 분께서는 ICPC 등의 알고리즘 대회에 좋은 성적을 거두기 위해서 일 것 같습니다.

저는 프론트엔드 개발자가 되고 싶습니다. 많은 프로그래밍 분야 중에 프론트엔드를 선택한 이유 중의 일부는 방대한 Javascript 생태계와 활발한 커뮤니티, 문법의 자유로움입니다.

수학을 좋아하고 알고리즘도 좋아하지만, 알고리즘 대회에 입상을 꿈꾸거나 이를 전공으로 하는 대학원에 들어가기 위해서 알고리즘을 공부하지 않습니다. 저는 프론트엔드 개발자로서 갖추어야 할 기본 알고리즘 소양을 기르기 위해서, Javascript에 대한 문법적, 실체적 지식을 갖추기 위해서, 그리고 신입 개발자로 입사하기 위한 코딩테스트를 통과하기 위해서 알고리즘을 공부합니다.

다행히 요즘 빅테크기업들은 코딩테스트용 언어로 Javascript를 지원하는 경우가 꽤나 있는 것 같습니다. 적어도 제가 지원하고 싶어하는 기업들은 꽤 지원을 하고 있습니다. 코딩테스트에서 정식으로 Javascript를 지원하는 이상, 느린 속도로 인해 시간 초과가 발생할 걱정은 하지 않아도 되는 것 같습니다. (제대로 된 알고리즘으로 문제를 풀었다는 가정하에서...)

따라서, 프론트엔드 개발자로서 계속 사용하게 될 Javascript에 대한 지식을 함양하기 위해서는 Javascript로 코딩테스트를 준비하는 것도 괜찮은 선택이라고 생각합니다. 또한, C++, Python, Java에 대한 어느 정도의 기초 지식이 있다면, 막히는 문제가 있다면 다른 언어로 작성된 해답을 보면서 문제 해결의 아이디어를 얻을 수 있습니다.
이때까지 Baekjoon Online Judge에서 Javascript로 약 100문제 가량 풀었지만, Javascript라서 못 푼 문제는 딱 한 문제 밖에 없었습니다. (2293번 동전1: 시간 제한이 0.5초로 극도로 짧습니다. 혹시 Javascript로 문제를 푸셨다면 저에게도 방법 공유를 부탁드립니다...)

Javascript로 코딩테스트를 준비하는데 자료가 빈약한 것은 사실입니다

콘솔창으로부터의 입력도 처음에는 어떻게 해야 할지 막막할 수 있습니다. nodejs로 express 서버는 돌려보았지만, 입출력 스트림을 다뤄보는 일은 잘 없으니까요.
또한 c++의 STL에 비해 Javascript가 기본적으로 제공하는 자료구조나 내장 유틸 함수가 부족한 것도 사실입니다.
따라서 앞으로 제가 Javascript로 문제를 풀면서 적용한 노하우, 앞으로 풀어가면서 깨닫게 되는 팁에 대해서 정리해보고자 합니다.

참고로, 저는 '실행속도' 보다는 'ES6+ 문법'에 조금 더 초점을 맞춘 풀이 및 팁을 말씀드릴 예정입니다. '실행속도 따위는 신경쓰지 않겠어' 보다는, 어차피 '실행속도'를 고려한다면 다른 언어를 선택하는 것이 맞기 때문에, 조금 실행속도가 느리더라도 Javascript다운 코드로 문제를 풀어갈 계획입니다.

결론: 저와 같은 생각을 가지시고 Javascript로 코딩테스트를 준비하겠다는 분은 앞으로 제가 제시하는 팁을 참고해주시면 감사하겠습니다.

도입

코딩테스트는 일반적으로 아래의 3단계로 구성됩니다.
1. 입력: 주어진 입력을 받아들여 프로그램의 자료구조에 저장하기
2. 계산: 알고리즘을 활용하여 정답을 계산하기
3. 출력: 정답을 주어진 형식에 맞게끔 출력하기

Baekjoon Online Judge(이하 "BOJ")는 위와 같은 흐름이나,
Programmers 같은 경우에는 2. 계산에 더욱 초점을 맞추고자
1. 입력과 3. 출력을 간소화하여 1. 입력의 경우, 함수의 인자(parameter)로 주어지며
3. 출력의 경우 정답을 함수의 반환값(return value)으로 하는 것으로 대체하였습니다.

Programmers 같은 경우에는, 입출력 처리에 골머리를 썩을 필요가 없으나,
BOJ의 경우에는 입출력 처리로 인해 처음에 고전할 수 있습니다.

따라서 Javascript(Node.js)로 코딩테스트 준비시의 입출력 처리방법에 대해서 정리해보겠습니다.

0. "use strict"

입출력에 앞서서, 간단하게 "use strict"에 대해서 언급하고자 합니다.
strict mode 사용시, 기존에는 조용히 무시되던 에러들을 throwing하고, 엔진의 최적화 작업을 어렵게 만드는 실수들을 바로잡아, 가끔씩 strict mode의 코드는 non-strict mode의 동일한 코드보다 더 빨리 작동합니다.

따라서, 항상 "use strict"를 사용합시다.

참고: Strict mode

1. 입력

BOJ에서 Node.js의 입출력에 대하여 아래와 같이 언어 도움말에서 제공하고 있습니다.
출처: 도움말-컴파일 또는 실행 옵션, 컴파일러 버전, 언어 도움말

var fs = require('fs'); 
var input = fs.readFileSync('/dev/stdin').toString().split(' '); 
var a = parseInt(input[0]); 
var b = parseInt(input[1]);
console.log(a+b);

1-1. fs vs readline

결론: 항상 fs모듈을 사용합니다.

코딩테스트에서 입력을 받은 뒤에 계산을 하고 출력을 합니다. 계산 도중에 인터랙티브하게 유저로부터 입력을 받는 일이 없습니다. 따라서, 이벤트 드리븐 방식의 복잡한 readline 모듈을 사용할 필요가 전혀 없습니다. 항상 fs.readFileSync(0, "utf8")을 사용합시다.
참고: fs.readFileSync 예시

아래는 fs모듈과 readline모듈에 대하여 블로그를 작성하기 위하여 공부하면서 정리한 내용인데, 크게 중요하지는 않으므로 스킵하셔도 좋습니다.

1-1-1. fs 모듈

fs는 file system을 의미합니다. POSIX 시스템에서는 모든 프로세스에 대해 커널이 현재 열려 있는 파일 및 리소스 테이블을 유지 관리합니다. 열려 있는 각 파일에는 파일 설명자(file descriptor)라는 간단한 숫자 식별자가 할당됩니다. 시스템 수준에서 모든 파일 시스템 작업은 이러한 파일 설명자를 사용하여 각 특정 파일을 식별하고 추적합니다. 윈도우즈 시스템은 리소스를 추적하기 위해 다르지만 개념적으로 유사한 메커니즘을 사용합니다. 사용자를 위한 작업을 단순화하기 위해 Node.js는 운영 체제 간의 특정 차이를 추상화하고 열려 있는 모든 파일에 숫자 파일 설명자를 할당합니다. 참고로, 표준입력(stdin: standard input)의 파일 설명자는 0 입니다.

readFile함수는 비동기적으로 파일의 전체를 읽으므로 파일을 읽어들이기가 완료된 후에 콜백 함수를 통하여 다음 스텝을 진행할 수 있는 반면, readFileSync는 동기적으로 파일을 읽어들입니다. 어차피 입력을 다 받아야만 계산을 진행할 수 있으므로, 동기적 처리 방식이 코드도 간결하고 이해하기 편합니다.

fs.readFileSync(path[, options])

• path: <string> | <Buffer> | <URL> | <integer> filename or file descriptor
• options: <Object> | <string>
  • encoding <string> | <null> Default: null
  • flag <string> See support of file system flags. Default: 'r'.
• Returns: <string> | <Buffer>

const fs = require("fs");

// 개행문자(\n)로 구분된 각 행을 요소로 가지는 배열을 반환. 
// 인코딩을 명시적으로 넘기지 않은 경우에는 raw Buffer가 반환되므로 
// toString()함수를 호출하여 string으로 변환하여야 한다.
const input1 = fs.readFileSync(0).toString().split("\n"); 

// options으로 인코딩을 string 자료형으로 넘기는 경우, string을 반환한다.
const input2 = fs.readFileSync(0, "utf8").split("\n"); 

// input2와 동일
const input3 = fs.readFileSync(0, {encoding: "utf8"}).split("\n");

참고: Node.js v14.15.4 Documentation - File system

1-1-2. readline 모듈

readline모듈은 Readable 스트림(예를 들어 process.stdin 또는 file Stream)으로부터 한 번에 한 줄씩 데이터를 읽어들이기 위한 인터페이스를 제공합니다.

const readline = require('readline');

const rl = readline.createInterface({
  input: process.stdin,
  output: process.stdout
});

'line'이벤트는 입력 스트림이 줄바꿈(end-of-line) 입력(\n, \r, \r\n)을 받을 때마다 발생합니다. 주로 유저가 'Enter'나 'Return'을 입력한 경우에 발생합니다. 리스너 함수는 유저로부터 입력된 한 줄을 인자로 하여 호출됩니다.

rl.on('line', (input) => {
  console.log(`Received: ${input}`);
});

'close'이벤트는 아래 중 하나가 발생할 때 발생합니다.

• rl.close() 함수가 호출되어 readline.Interface 인스턴스가 입출력 스트림의 권한을 포기한 상태일 때
• 입력 스트림이 'end'이벤트를 받은 경우
• 입력 스트림이 'Ctrl'+'D' (EOT: end-of-transmission)을 받은 경우
• 입력 스트림이 'Ctrl'+'C' (SIGINT)를 받았고, 'SIGINT' 이벤트 리스너가 readline.Interface 인스턴스에 등록되지 않은 경우

리스너 함수는 아무런 인자를 넘겨받지 않고 호출됩니다.
readline.Interface객체는 'close'이벤트가 발생된 후에 완료됩니다.

따라서, readline 모듈을 사용할 경우에는, 각 줄이 입력될 때마다 'line' 이벤트가 매번 발생하여 이를 변수에 저장하며, 'close' 이벤트가 발생한 경우 저장된 변수를 가지고 계산을 진행하게 됩니다.

이를 코드로 나타내면 아래와 같이 되는데, 굳이 fs모듈의 readFileSync를 쓰는 것이 훨씬 간결하고 신경 쓸 부분이 적다는 것을 알 수 있을 것입니다.

const readline = require('readline');
const rl = readline.createInterface({
  input: process.stdin,
  output: process.stdout,
});

rl.on('line', (line) => {
  // line을 가공하여 변수에 저장
  
}).on('close', () => {
  // 저장된 변수를 이용하여 계산 후 출력
});

1-2. string -> number 자료형 변환: Number vs new Number vs parseInt

결론: Number 또는 parseInt를 사용합시다.

1-2-1. Number vs new Number

Number 는 function으로서 작용하여 primitive type을 반환하지만, new Number는 constructor로서 작용하여 Object를 반환합니다.

큰 차이가 없어 보이지만, 차이는 있습니다.
1. Object는 boolean context에서 항상 true입니다. 따라서 이를 의식하지 않고 코딩을 하다보면 일반적으로 생각하는 것과 다른 움직임을 보일 수 있습니다.

const a = Number("0");
const b = new Number("0");

if (a) {   // false 이므로 조건문 내부는 실행되지 아니함
...
}

if (b) { // `Object([Number: 0])`는 boolean context에서 `true`이므로 조건문 내부가 실행됨
...
}

1. Object와 primitive type 의 === 비교시 false가 반환됩니다.

const a = new Number('123'); // a === 123 is false
const b = Number('123');     // b === 123 is true
console.log(a === 123); // false
console.log(b === 123); // true

console.log(a instanceof Number); // true
console.log(b instanceof Number); // false

혼란을 피하기 위하여 new Number는 사용하지 않습니다.

1-2-2. Number vs parseInt

parseInt는 브라우저별 내부 구현 방법에 따라 다르게 해석될 수 있기 때문에 명시적으로 radix를 기재하여야 합니다. 저희는 Node.js로 코딩테스트를 준비하기 때문에 크게 상관은 없지만, 알아두시면 좋을 것 같습니다.

parseInt(str, 10)과 Number(str)의 차이는 아래와 같습니다.

const str = "10x";
console.log(parseInt(str, 10)); // 10
console.log(Number(str)); // NaN

경험적으로 parseInt와 Number의 실행속도차이는 미미한 것 같습니다.
저는 개인적으로 Number를 사용합니다. radix를 기재하는게 귀찮기도 하고, 그냥 익숙해서요.
코딩테스트에서 입력값의 정확성은 보장되므로 어떤 것을 쓰더라도 문제 없을 것 같습니다.

const fs = require('fs');
const input = fs.readFileSync('/dev/stdin').toString().split(' ');
const a = Number(input[0]); // 또는 parseInt(input[0], 10);
const b = Number(input[1]); // 또는 parseInt(input[1], 10);
console.log(a+b);

(참고: new Number() vs Number())

1-3. ES6+

BOJ에서 Node.js의 실행환경은 아래와 같습니다.

node.js
언어 번호: 17
실행: node Main.js
버전: v14.15.0
시간 제한: ×3+2초
메모리 제한: ×2MB

Node.js의 현재(2021-01-12 Tue) 기준 최신 버젼은 15.5.1이며 LTS는 14.15.4입니다. 따라서, BOJ에서 v14.15.0 Node.js 환경을 제공한다는 것은, 안정적이고 신뢰도 높은 최신 기능들 대부분을 사용할 수 있다는 뜻입니다.

1-3-1. const, let

Javascript로 코딩테스트를 제출하는 사람들 중 많은 사람들의 실수가, 함수 스코프 var와 블록 스코프 const, let을 혼용하는 점이라고 합니다.
자바스크립트 코딩 테스트에서 가장 많이하는 실수들

위의 예제에서는 일관성있게 var를 사용하였습니다. 그러나 알고리즘 문제 풀이시 함수 스코프를 써야만 할 일은 없을 것 같습니다. 어느 곳에서나 접근하고 싶다면 그냥 최상위 스코프에서 변수를 정의하면 됩니다. 또한 BOJ에서의 Node.js 실행환경에서는 ES6를 지원하므로 블록 스코프인 const, let을 쓰는 것이 좋을 것 같습니다.

const fs = require('fs');
const input = fs.readFileSync('/dev/stdin').toString().split(' ');
const a = parseInt(input[0]);
const b = parseInt(input[1]);
console.log(a+b);

개인적으로 입력값은 불변값으로 다루는 것이 좋다고 생각합니다. 입력값은 말그대로 문제에서 주어지는 값이므로, 이를 변경할 일은 없는 것이 일반적입니다. 후에 for문이나 조건문 등에서 사용될 때에 입력값을 변경하여 오류가 생기는 일을 막을 수 있습니다. 따라서 모두 const로 변수를 선언합니다.

1-3-2. destructuring

destructing을 이용한다면 a,b를 아래와 같이 정의할 수 있습니다.

const fs = require('fs');
const input = fs.readFileSync(0).toString().split(' ');
const [a,b] = input.map((s) => parseInt(s, 10));
console.log(a+b);

참고로 Number함수를 활용하여 아래와 같이 한 줄로도 a,b를 정의할 수 있습니다.

const [a, b] = require('fs').readFileSync(0, "utf8").split(" ").map(Number);
console.log(a+b);

2. 출력

console.log를 이용해서 출력을 하면 됩니다.
다만,console.log는 호출시 많은 시간이 소요되는 함수이므로, 백트래킹과 같이 알고리즘 중간중간에 출력을 하는 경우에는 배열이나 string에 출력값을 저장해두었다가 계산 종료후 한번에 출력을 해주는 것이 좋습니다.

아래는 BOJ 15649번 문제 N과 M (1)의 채점결과입니다. 위에는 계산 종료후 코드의 마지막에 한번만 출력을 해준 경우이고, 아래는 계산 중간중간에 계속해서 출력을 해준 경우입니다. 보시다시피 실행 시간의 차이가 엄청 많이 나신다는 것을 알 수 있습니다.

// 계산 종료후 마지막에 한번만 출력
...
let print = "";

(function rec(lev) {
  if (lev === M) {
    print += `${arr.join(" ")}\n`; // depth가 M일 때마다 print에 출력 값 저장
    return;
  }

  ...
  rec(lev + 1);
  ...
})(0);

console.log(print); // 계산 종료후 마지막에 출력

// 계산 중간중간에 출력
...

(function rec(lev) {
  if (lev === M) {
    console.log(`${arr.join(" ")}\n`); // depth가 M일 때마다 print에 출력 값 저장
    return;
  }

  ...
  rec(lev + 1);
  ...
})(0);

※ process.stdout.write vs console.log
Writable 스트림인 process.stdout의 write함수를 이용하여 출력을 할 수 있습니다. console.log도 내부적으로 process.stdout.write를 이용하여 출력한다고 합니다. 하지만 경험적으로 console.log와 process.stdout.write의 실행속도 차이를 느끼지 못하였습니다. console.log, process.stdout.write 모두 무거운 함수 호출이므로, 이를 최소화하기 위하여 배열이나 string에 출력값을 저장해두는 테크닉이 더 실행속도 단축에 도움이 되는 것 같습니다.

참고URL: Node.js v14.15.4 Documentation - Writable Stream: writable.write(chunk[, encoding][, callback])