숫자 카드 2 (백준 코딩테스트 10816번, 파라메트릭 서치, Node.JS 풀이)

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

 

 

문제 유형:

파라메트릭 서치

 

 

문제 요약:

숫자 카드는 정수 하나가 적혀져 있는 카드이다. 상근이는 숫자 카드 N개를 가지고 있다. 정수 M개가 주어졌을 때, 이 수가 적혀있는 숫자 카드를 상근이가 몇 개 가지고 있는지 구하는 프로그램을 작성하시오.

 

 

입출력 예 (입력 / 출력):

//입력
10
6 3 2 10 10 10 -10 -10 7 3
8
10 9 -5 2 3 4 5 -10


//출력
3 0 0 1 2 0 0 2

 

 

문제 풀이 전략:

해결 아이디어:

1. 해시로 풀기 : 그저 원시적으로 배열을 순회하면서 그 값이 몇 번 나왔는지 세기. 시간복잡도 O(n**2)
2. 이진 탐색으로 풀기: 정렬된 배열이라면 똑같은 값을 가진 첫번째 데이터의 index와 똑같은 값을 가진 마지막 데이터의 index를 가지고 lastIdx - startIdx + 1로 구할 수 있다.

 

 

 

내 풀이:

// 해시로 풀기(시간 초과 코드)
let fs = require("fs");
let input = fs.readFileSync("dev/stdin").toString().split("\n");

const toSort = input[1].split(" ").map(Number).sort((a, b) => a - b); // 가진 카드더미
const target = input[3].split(" ").map(Number); // 세야할 숫자 카드 목록
const obj = {}; // 카운트해서 기록해둘 객체

toSort.forEach((item) => { //각각의 인자들을 모두 검사
  if (target.includes(item)) { // target에 item이 포함이 되어 있으면
    obj[item] = (obj[item] || 0) + 1; //obj[key] = value꼴로 0, 1, 2... 카운트 개시
  }
});

let ans = "";
for (i = 0; i < target.length; i++) {
  ans += (obj[target[i]] || 0) + " "; //객체에 있는 밸류를 한 줄에 나오도록 공백문자로 조합
}
console.log(ans);
// 생각대로 답은 나오지만 시간초과.
// 데이터가 10만개 이상일 때부터 시간초과가 날거 같지만 직관적으로 떠오른 해결방법이라 한 번 해보았다.

 

//이진 탐색으로 풀기(통과)
let fs = require("fs");
let input = fs.readFileSync("input.txt").toString().split("\n");

const toSort = input[1].split(" ").map(Number).sort((a, b) => a - b); // 일단 입력값 정렬
const targets = input[3].split(" ").map(Number); // 비교값
const ans = []; // 비교값에 있는 값이 입력값에 얼마나 있는지 기입할 배열

for (ta of targets) { // 세야할 숫자 목록들 중 하나를 뽑는다.
  let start = 0; // 0을 이진탐색의 시작 인덱스 값으로 설정
  let end = toSort.length - 1; // 배열 마지막 인덱스를 이진탐색의 끝 인덱스 값으로 설정
  
  let startIdx; //ta 중에 첫 인덱스가 무엇인지 (돌아보니 좋은 변수 네이밍은 아닌듯..)

  while (start <= end) { //startIdx를 구하는 while문. start와 end가 작거나 같은 것을 계속 구하면(start와 end가 같아질때까지) 결국 해당값의 첫번째 값을 구할 수 있다.
    let mid = parseInt((start + end) / 2); // start와 end의 중간 값을 구함
    if (ta === toSort[mid]) { // **ta과 toSort[mid]가 맞다면,**
      startIdx = mid; // 위에 선언했던 startIdx에 mid 할당!
      end = mid - 1;
    } else if (ta < toSort[mid]) { // **ta가 toSort[mid]보다 작다면,**
      end = mid - 1; // end를 미드값보다 1 작게 설정
    } else { // **ta가 toSort[mid]보다 크다면,**
      start = mid + 1; // start를 미드값보다 1 크게 설정
    }
  }

  start = 0; // 다시 start값 초기화
  end = toSort.length - 1; // 다시 mid값 초기화

  let endIdx; // 이제 ta가 등장하는 마지막 인덱스를 구할 차례

  while (start <= end) { //lastIdx를 구하는 while문
    let mid = parseInt((start + end) / 2) || 0;
    if (ta === toSort[mid]) { // ta가 toSort[mid]와 같다면
      endIdx = mid; // 위에 선언했던 endIdx에 mid 할당!
      start = mid + 1;
    } else if (ta < toSort[mid]) { // **ta가 toSort[mid]보다 작다면,**
      end = mid - 1; // end값을 mid보다 1 아래 설정
    } else { // **ta가 toSort[mid]보다 크다면,**
      start = mid + 1; // start값을 mid보다 1 크게 설정
    }
  }
  const answerCnt = endIdx - startIdx + 1 || 0;
  // toSort배열에 ta가 없는 경우 startIdx와 endIdx에 값이 안 들어와 undefined인 경우가 있는데
  // 그 땐 배열에 없으므로 0을 할당
  ans.push(answerCnt); // 정답 배열에 push
}
console.log(ans.join(" ")); // 공백을 사이에 두고 join 후 출력

/* divide and conquer로 접근..
1. 일단 최댓값과 최솟값을 만드는 코드를 먼저 구하고 '최댓값 - 최솟값 + 1'로 갯수를 구함
2. 모든 target 배열을 순회하면서 갯수를 저장함 */