[BEAKJOON / node.js] 10816 숫자 카드 2

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

//test.txt
10
6 3 2 10 10 10 -10 -10 7 3
8
10 9 -5 2 3 4 5 -10

---

sol1

let input = require('fs').readFileSync('test.txt').toString().trim().split('\n');
let N = input[1]
    .split(' ')
    .map(Number)
    .reduce((acc,cur) => {
        acc[cur] = (acc[cur]||0) + 1;
        return acc
    },{});
let M = input[3]
    .split(' ')
    .map(Number)
    .map(v => N[v] ? N[v] : 0)
    .join(' ');
console.log(M);
// 3 0 0 1 2 0 0 2

 

 

중복 횟수를 담은 객체를 만들고 가지고 있는지 확인해야 할 카드 배열에서 객체에 key가 있다면 value를 받고 없다면 0을 받도록 한다.

 

1.

let N = input[1]
    .split(' ')
    .map(Number)
    .reduce((acc,cur) => {
        acc[cur] = (acc[cur]||0) + 1;
        return acc
    },{});
console.log(N)
//{ '2': 1, '3': 2, '6': 1, '7': 1, '10': 3, '-10': 2 }

객체에 바로 담기 위해 reducd() 메서드를 사용했다.

 

2.

let M = input[3]
    .split(' ')
    .map(Number)
    .map(v => N[v] ? N[v] : 0)
    .join(' ');
console.log(M);
//3 0 0 1 2 0 0 2

삼항 연산자로 key값의 유무를 확인하고 출력한다.

---

 

sol2

let input = require('fs').readFileSync('test.txt').toString().trim().split('\n');
let N = input[1].split(' ').map(Number);
let M = input[3].split(' ').map(Number);
let map = new Map();
N.forEach(el => {
  if(map.has(el)) map.set(el,map.get(el)+1);
  else map.set(el,1);
});
let answer = [];
M.forEach(el => answer.push(map.get(el)||0));
console.log(answer.join(' '));

Map을  이용해 중복을 체크해서 저장해두고 M 배열을 돌며 map에 있다면 value를, 없다면 0을 받도록 한다.

 

1.

let map = new Map();
N.forEach(el => {
  if(map.has(el)) map.set(el,map.get(el)+1);
  else map.set(el,1);
});
console.log(map);
// Map(6) { 6 => 1, 3 => 2, 2 => 1, 10 => 3, -10 => 2, 7 => 1 }

---

sol3

let input = require('fs').readFileSync('test.txt').toString().trim().split('\n');

const solution = (input) => {
    const N = +input[0];
    const A = input[1].split(" ").map(Number).sort((a,b) => a-b);
    const B = input[3].split(" ").map(Number);

    let answer = [];
    B.forEach(
        value => {
            const loweridx = lower(A, value, 0, N-1);
            const upperidx = upper(A, value, 0, N-1);
            let result = 0
            if (loweridx !== -1 && upperidx !== -1 ){
                result = upperidx-loweridx+1
            } else {
                result = 0
            }
            answer.push(result);
        }
    );
    console.log(answer.join(' '));
};

const lower = (array, target, start, end) => {
  let answer = -1;
  while(start<=end){
      mid = Math.floor((start+end)/2)
      if(array[mid] === target){
          answer = mid
          end = mid -1 ;
      }else if(array[mid]>target){
          end = mid-1;
      }else{
          start = mid+1
      }
  }
  return answer;
};

const upper = (array, target, start, end) => {
  let answer = -1;
  while(start<=end){
      mid = Math.floor((start+end)/2)
      if(array[mid] === target){
          answer = mid
          start = mid + 1;
      }else if(array[mid]>target){
          end = mid-1;
      }else{
          start = mid+1
      }
  }
  return answer;
};

solution(input);
// 3 0 0 1 2 0 0 2

이진 탐색을 이용했다. 이진 탐색을 위해 오름차순 정렬을 해줘야 하며 중복된 숫자의 시작 index에서 끝 index 를 빼고 1을 더해주면 중복횟수를 구할 수 있다. 시작 Index 와 끝 index를 구하기 위한 함수를 각각 만들어 사용했다.

 

---

sol1,2,3 순서

 sol1 의 경우 중복을 객체로 확인했고 sol2 는 Map 에 담아서 확인했는데 속도차이가 나는 편이다. reduce메서드를 통해 바로 객체로 담는게 편하긴 하지만 Set 이나 Map을 이용하는 방법도 익숙해져야 겠다.

 sol3의 경우 오름차순으로 정렬시키고 시작 index, 끝 index 를 찾기 위한 이분탐색을 돌리느라 배열을 총 3번 돌게 되어 시간이 더 많이 걸리지 않았나싶다. 비슷한 논리를 해결하는데 도움이 되므로 탐색 방법 자체는 익혀두도록 한다.