[백준] 숫자 카드 2 (javascript)

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

10816번: 숫자 카드 2

 

🤔 해결방법

1. 상근이가 가지고 있는 숫자들을 haveNumber에, 몇 개 가지고 있는지 체크할 숫자를 checkNumber에 넣는다.

2. haveNumber의 숫자 각각의 개수를 object 객체에 담는데 이미 있으면 value+1, 없으면 1을 value로 넣는다.

3. checkNumber에 담긴 숫자가 object에 있으면 그 개수를, 없으면 0을 배열 answer에 넣는다.

4. answer의 길이를 출력한다.

 

 

🔑 풀이

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

  const haveNumber = input[1].split(" ").map(Number); //가지고 있는 숫자
  const checkNumber = input[3].split(" ").map(Number); //체크 할 숫자

  const object = {}; //haveNumber에 담긴 숫자들을 각 개수와 함께 담을 객체
  haveNumber.forEach((n) => {
    object[n] ? object[n]++ : (object[n] = 1); //이미 있으면 +1 없으면 1을 넣음
  });

  const answer = [];
  checkNumber.forEach((n) => {
    answer.push(object[n] ? object[n] : 0); //checkNumber에 담긴 숫자가 object에 있으면 그 개수를, 없으면 0을 answer에 넣음
  });
  console.log(answer.join(" "));

 

 

😭 삽질

처음에 다음과 같이 이중 for문으로 checkNumber를 모든 haveNumber와 비교하는 코드를 짰는데 백준에 제출하니 시간초과가 떴다.

haveNumber의 모든 숫자와 비교하는건 비효율적이라 시간초과를 예상했었지만 그냥 제출해봤다..ㅋㅋ

역시나 호락호락하지 않은 백준😂

 const input = require("fs")
     .readFileSync("/dev/stdin")
     .toString()
     .trim()
     .split("\n")

  const haveNumber = input[1].split(" ").map(Number); //가지고 있는 숫자
  const checkNumber = input[3].split(" ").map(Number); //체크할 숫자
  let answer = [];

  function solution(haveNumber, checkNumber) {
    for (let i = 0; i < checkNumber.length; i++) {
      let count = 0;
      for (num of haveNumber) {
        //haveNumber의 요소와 같은 값이면 count +1
        if (checkNumber[i] === num) count++;
      }
      answer.push(count);
    }
    console.log(answer.join(" "));
  }

  solution(haveNumber, checkNumber);

 

다음과 같이 객체를 사용하면 모든 숫자와 비교하지 않아도 된다. 

haveNumber에 담긴 숫자들을 각 개수와 함께 key, value로 객체에 담아 checkNumber의 숫자들이 그 객체에 있는 지 체크해주는 것이다.

 

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

  const haveNumber = input[1].split(" ").map(Number); //가지고 있는 숫자
  const checkNumber = input[3].split(" ").map(Number); //체크할 숫자

  const object = {}; //haveNumber에 담긴 숫자들을 각 개수와 함께 담을 객체
  haveNumber.forEach((n) => {
    object[n] ? object[n]++ : (object[n] = 1); //이미 있으면 +1 없으면 1을 넣음
  });

  const answer = [];
  checkNumber.forEach((n) => {
    answer.push(object[n] ? object[n] : 0); //checkNumber에 담긴 숫자가 object에 있으면 그 개수를, 없으면 0을 answer에 넣음
  });
  console.log(answer.join(" "));

 

 

 

haveNumber에 담긴 숫자들을 차례로 object에 넣는데 이미 해당 숫자가 있으면 value에 1을 더해주고 없으면 value를 1로 해서 넣는다.

그리고 checkNumber에 담긴 숫자들을 차례로 object와 비교하여 object에 있는 숫자면 value인 개수를, 없으면 0을 빈 배열인 answer에 넣고 answer를 join하여 출력한다.

 

검색해보니 객체 대신 es6에 새로 등장한 map을 사용하는 방법도 있었다.

map을 사용하니 메모리와 시간이 훨씬 적게 들었다.

map사용에 익숙해져야겠다.

const input = require("fs")
    .readFileSync("/dev/stdin")
    .toString()
    .trim()
    .split("\n");
  const haveNumber = input[1].split(" ").map(Number); //가지고 있는 숫자
  const checkNumber = input[3].split(" ").map(Number); //체크 할 숫자

  const map = new Map();
  haveNumber.forEach((n) => {
    map.has(n) ? map.set(n, map.get(n) + 1) : map.set(n, 1);
  });

  const answer = [];
  checkNumber.forEach((n) => {
    answer.push(map.has(n) ? map.get(n) : 0);
  });

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

 

이진탐색 방법을 사용한 풀이도 발견했다.

다음 그림에서 아래 방법(sequential search)이 내가 처음에 이중 for문을 사용해 모든 요소를 비교하는 코드라면 윗 방법(binary search)은 중앙값을 사용하여 훨씬 더 빠르게 원하는 숫자를 찾는 이진탐색 방법이다.

 

출처 : https://blog.penjee.com/binary-vs-linear-search-animated-gifs/

 

이진탐색 방법 풀이는 다음 블로그를 참고하자.

 

https://gywlsp.github.io/boj/10815/

백준 10815번 숫자 카드 - node.js