백준 10816 Js 숫자카드2

문제링크

https://www.acmicpc.net/problem/10816

10816번: 숫자 카드 2

 

틀린 내 코드

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

const N = Number(input.shift());
const NCard = input.shift().split(" ");
const M = Number(input.shift());
const MCard = input.shift().split(" ");

const targetAry = MCard.slice().sort((a, b) => a - b);

let obj = {};

for (let key in MCard) {
  obj[MCard[key]] = 0;
}

function binary(targetAry, target) {
  let result = 0;

  let start = 0;
  let end = targetAry.length - 1;

  while (start <= end) {
    let mid = Math.floor((start + end) / 2);

    if (+targetAry[mid] > +target) end = mid - 1;
    else start = mid + 1;

    if (+targetAry[mid] === +target) result = target;
  }
  return result;
}

// ["-10", "-10", "2", "3", "3", "6", "7", "10", "10", "10"];

NCard.forEach((e) => {
  let result = binary(targetAry, e);

  obj = {
    ...obj,
    [e]: (e === result && obj[e] + 1) || 0,
  };
});

const filter = Object.entries(obj);

let answer = [];

for (let i = 0; i < MCard.length; i++) {
  for (let j = 0; j < filter.length; j++) {
    if (MCard[i] === filter[j][0]) {
      answer.push(filter[j][1]);
    }
  }
}

console.log(answer.join(" "));


// {
//   '2': 1,
//   '3': 2,
//   '4': 0,
//   '5': 0,
//   '6': 0,
//   '7': 0,
//   '9': 0,
//   '10': 3,
//   '-5': 0,
//   '-10': 2
// }
// 3 0 0 1 2 0 0 2

로직

 

1.  주어진 카드를 value 로 0을 갖는 객체로 만들어준다. 보통 중복검사 할때 쓰는 방법인데 카운팅하려고 사용했다.

2. 이진탐색으로 찾은 값이 있으면 객체에 카운팅을 해주었다.

3. 객체로 만들다보니 답지에 나온 원본 배열의 순서가 깨져있었다.

4. 객체를 다시 배열로 만들고 이중 for 문으로 M 카드에서 객체에 있는 값이 있으면 카운팅을 다시해주었다.

 

테케는 통과했고 이중 for문 등등 속도에서 틀릴거라 생각하고 돌려봤는데 메모리 초과가 나왔다.

 

 

정답코드

const input = require("fs")
  .readFileSync(filePath)
  .toString()
  .trim()
  .split("\n");

const K = input[1].split(" ").map((v) => +v);
const M = input[3].split(" ").map((v) => +v);

K.sort((a, b) => a - b);
let N = [[K[0], 1]];
for (let i = 1; i < K.length; i++) {
  if (K[i - 1] == K[i]) {
    N[N.length - 1][1]++;
  } else {
    N.push([K[i], 1]);
  }
}

console.log(N);

let answer = [];
M.forEach((v) => {
  let left = 0;
  let right = N.length - 1;
  let find = false;
  while (left <= right) {
    let mid = Math.floor((right + left) / 2);
    if (N[mid][0] > v) {
      right = mid - 1;
    } else if (N[mid][0] < v) {
      left = mid + 1;
    } else {
      find = true;
      answer.push(N[mid][1]);
      break;
    }
  }
  if (!find) answer.push(0);
});

console.log(answer.join(" "));

 

로직

 

나는 객체를 사용해서 카운팅을 했는데, 정답코드는 배열을 이중 배열로 만들고 카운팅을 했다...