[이진탐색] 숫자 카드 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` 환경에서 너무 출력문이 많아선 안됨!
```javascript
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(" "));