[이진탐색] 숫자 카드 2

[ericagong]

⭐ 성찰

1. Map에서 key 개수를 초기값 설정하며 카운팅하는 방법: m.set(key, m.get(key) + 1 || 1)
2. Map에서 존재하지 않는 값에 접근하면, undefined 반환되므로 Map.prototype.has(key)로 존재여부 확인하는 방어코드` 추가
3. TC 환경에서 너무 출력문이 많으면 시간초과나므로, 최종적으로 출력 한 번만 하도록 처리
4. 정렬된 배열에서 특정 숫자 개수 세는 함수 getCountRangeOf(rightVal, leftVal) 익혀두기

function lowerBound(arr, val, s, e) {
  while (s < e) {
    const m = parseInt((s + e) / 2);
    if (arr[m] >= val) e = m;
    else s = m + 1;
  }
  // console.log(`lowerBound: ${e}`)
  return e;
}

function upperBound(arr, val, s, e) {
  while (s < e) {
    const m = parseInt((s + e) / 2);
    if (arr[m] > val) e = m;
    else s = m + 1;
  }
  // console.log(`upperBound: ${e}`)
  return e;
}

function countByRange(arr, leftVal, rightVal) {
  const leftIdx = lowerBound(arr, leftVal, 0, arr.length);
  const rightIdx = upperBound(arr, rightVal, 0, arr.length);
  return rightIdx - leftIdx;
}

❓ 문제 상황

숫자 카드 2

👨‍💻 문제 해결: 시간 복잡도를 고려해 풀이 방법 정하기

✅ 1차 풀이: Map을 이용해서 등장 횟수 카운트

시간복잡도 O(N+N+N) = O(N), 최악의 경우 150만 -> 유효

1. 전체 카드를 순회하며 등장 횟수를 세서 map에 저장
2. 전체 숫자를 순회하며 등장 횟수를 배열에 저장
3. 배열을 문자열로 합쳐 반환 -> ⭐ TC 환경에서 너무 출력문이 많아선 안됨!

const fs = require('fs')
const inputs = fs.readFileSync('/dev/stdin').toString().split('\n')

const N = Number(inputs.shift())
const cards = inputs.shift().split(' ').map(Number)
const M = Number(inputs.shift())
const nums = inputs.shift().split(' ').map(Number)

const cnts = new Map()
cards.forEach((card) => {
  cnts.set(card, cnts.get(card) + 1 || 1)
})

const arr = []
nums.forEach((num) => {
  // 없는 경우, 처리
  if(cnts.has(num)) arr.push(cnts.get(num))
  else arr.push(0)
})

console.log(arr.join(' '))

[ericagong]

✅ 2차 풀이: lowerBound, upperBound 함수 통해 숫자 카운트

• 시간복잡도 O(NlogN + 2MlogN), 최악의 경우 200만 -> 유효

1. 이진 탐색을 위해 전체 카드를 정렬 - O(NlogN)
2. 전체 숫자에 대해 각각 lowerBound, upperBound를 찾아 개수 카운트 - O(2MlogN)
3. 배열을 문자열로 합쳐 반환 -> ⭐ TC 환경에서 너무 출력문이 많아선 안됨!

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

const N = Number(inputs.shift());
const cards = inputs.shift().split(" ").map(Number);
const M = Number(inputs.shift());
const nums = inputs.shift().split(" ").map(Number);

function lowerBound(arr, val, s, e) {
  while (s < e) {
    const m = parseInt((s + e) / 2);
    if (arr[m] >= val) e = m;
    else s = m + 1;
  }
  // console.log(`lowerBound: ${e}`)
  return e;
}

function upperBound(arr, val, s, e) {
  while (s < e) {
    const m = parseInt((s + e) / 2);
    if (arr[m] > val) e = m;
    else s = m + 1;
  }
  // console.log(`upperBound: ${e}`)
  return e;
}

function countByRange(arr, leftVal, rightVal) {
  const leftIdx = lowerBound(arr, leftVal, 0, arr.length);
  const rightIdx = upperBound(arr, rightVal, 0, arr.length);
  return rightIdx - leftIdx;
}

// 정렬 함수 필수
cards.sort((a, b) => a - b);

const counts = [];
nums.forEach((num) => {
  counts.push(countByRange(cards, num, num));
});

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