[백준] 2776번: 암기왕 (Node.js)

 

접근방식

쉽게 해결할줄 알았는데 자꾸 틀리더라구요.. 이유가 뭔지 보니까 시간복잡도가 중요한 문제인걸 뒤늦게 알았습니다!

 

테스트케이스에 있는 4 1 5 2 3을 배열로 [4, 1, 5, 2, 3]으로 만든 뒤 1 3 5 7 9 가 있는 배열에 includes를 해보았는데

시간복잡도가 중요한 문제에서는 비효율이더라구요.

그래서 Set과 has를 이용하여 문제를 풀었습니다!

 

Set이란?

Set은 자바스크립트에서 중복되지 않는 고유한 값들의 집합을 저장하는 데 사용되는 내장 객체입니다.

 

 

Set은 같은 값이 여러 번 추가될 수 없기 때문에, 자연스럽게 중복 값을 제거해줍니다!

그리고 내부적으로 해시 테이블을 사용하여 구현되므로, 특정 요소가 Set에 있는지 확인하는 작업(=>has())은 평균적으로 O(1)의 시간 복잡도를 가집니다.

 

그럼 여기서 또 궁금할겁니다!

O(1)의 시간 복잡도란?

상수 시간 복잡도라고도 불리며, 입력 크기와 상관없이 항상 일정한 시간이 걸리는 알고리즘을 의미하는데
데이터의 크기와 무관하게 항상 같은 시간이 걸립니다.
즉, 입력 데이터의 크기가 1이든, 1000이든, 100만이든, 실행 시간은 일정합니다.

 

 

풀이 ⏰

const readline = require("readline");

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

let input = [];

rl.on("line", function (line) {
  input.push(line);
}).on("close", function () {
  // 테스트케이스 갯수
  let tCase = input[0];
  // 테스트케이스 1기준으로 2번째와 4번째의 배열을 다뤄야합니다.
  // 테스트케이스 2기준으로 6번째와 8번째의 배열을 다뤄야합니다. 그렇기에 += 4를 해주기 위한 index입니다.
  let index = 0;
  // 결과값
  let result = [];
  for (let i = 0; i < tCase; i++) {
    // Set을 사용하여 오브젝트 형태의 입력값을 설정합니다.
    let note1 = new Set(input[index + 2].split(" ").map(Number));
    // 기존 배열 그대로 사용합니다.
    let note2 = input[index + 4].split(" ").map(Number);
    for (item of note2) {
      // note1은 Set 고유의 오브젝트 형태이므로 has함수를 사용하여 note1에 item이 있는지 확인합니다.
      if (note1.has(item)) {
        result.push(1);
      } else {
        result.push(0);
      }
    }
    index += 4;
  }
  console.log(result.join("\n"));
});

 

백준 2776번 링크

👉 https://www.acmicpc.net/problem/2776