BOJ - 10816 숫자 카드 2

1. 문제 : https://www.acmicpc.net/problem/10816

2. 문제 유형 : 이진 탐색, 해시맵

3. 문제 티어: 실버4

4. 문제 풀이

처음 생각한 문제 풀이 방법은 배열을 처음부터 끝까지 순회하면서 같은 값이 있을 시 카운트를 추가하고 그 추가한 것을 새로운 결괏값 배열에 담는 과정을 반복하는 것이었다.

 

따라서 처음 코드는 아래와 같았다.

const fs = require("fs");
let input = fs.readFileSync("/dev/stdin").toString().split("\n");
let N = Number(input[0]);
let first_arr = input[1].split(" ").map(Number);
let M = Number(input[2]);
let second_arr = input[3].split(" ").map(Number);

// 비교 후 count 하는 함수 생성
function compare(arr, targets){
    // 결과를 저장할 배열
    let result = [];
    // arr length 만큼 반복문 돌림
    for(let target of targets) {
        let count = 0;
        for(let num of arr){
            if(num === target) count++;
        }
        result.push(count);
    }
    // 만약 arr에서 i랑 target이 같으면 count ++ 
    
    // result 배열에 push 후 다시 처음으로 돌아감
}
let output = compare(first_arr, second_arr);
console.log(output.join(" "));

 

= 시간 초과가 난 코드이며 이를 위해 새로운 방법을 찾던 중 해시맵(딕셔너리)을 사용하여 구현하는 방법을 참고 하였다.

 

1) first_arr의 숫자들을 한 번씩만 순회하여 숫자의 갯수를 저장한다.(O(N))
  -> 딕셔너리를 사용해 각 숫자의 등장 횟수를 기록
2) second_arr의 숫자를 확인할 때, 딕셔너리에서 즉시 값을 가져온다.( O(1))

 -> 따라서 전체 시간 복잡도는 O(N+M)

 

// 해시맵을 사용한 버전
const fs = require("fs");
let input = fs.readFileSync("/dev/stdin").toString().split("\n");
let N = Number(input[0]);
let first_arr = input[1].split(" ").map(Number);
let M = Number(input[2]);
let second_arr = input[3].split(" ").map(Number);

// 해시맵(딕셔너리 함수)
function countWithMap(arr, targets) {
    let countMap = new Map(); // 맵 생성
    for(let num of arr){
        // 첫 번째 배열 순회 후 num과 그에 따른 value 값 저장 만약 value가 없으면 0 + 1
        countMap.set(num, (countMap.get(num) || 0 ) + 1);
    }
    // 결과를 담을 result 배열
    let result = [];
    // 두 번째 배열 순회하면서 첫 번째 배열 순회 시 저장했던 갯수 가져옴
    for(let target of targets) {
        result.push(countMap.get(target) || 0);
     }
     return result;
 }
 
let output = countWithMap(first_arr, second_arr);
console.log(output.join(" "));

 

 

* 이진 탐색 사용한 풀이

추가로 이진 탐색을 사용한 풀이도 있었다.

함수에 관한 설명은 아래와 같다.

1) Lower Bound 함수
 - 배열에서 특정 값 이상인 첫 위치를 찾는 함수.

 - 예를 들어 배열 [1,2,2,3,4] 에서 target = 2인 경우
  lowerBount(arr,2) 는 1(인덱스)을 반환함 (2가 처음 등장하는 위치)

 

2) Upper Bound 함수
 - 배열에서 특정 값보다 큰 위치를 찾는 함수

 - 예를 들어 배열 [1,2,2,3,4]에서 target = 2인 경우
 upperBound(arr,2)는 3(인덱스)를 반환함( 3이 처음 등장하는 위치)

 

3) 등장 횟수 계산

 - 특정 값의 개수 = upperBound - lowerBound로 계산할 수 있다.

 - 예를 들어 배열 [1,2,2,3,4]에서 : 
          target = 2 일 때 upperBound (2) = 3 , lowerBound(2) = 1 

          => 따라서 2의 갯수는 3- 1 = 2

 

4) 정답 코드

const fs = require("fs");
let input = fs.readFileSync("/dev/stdin").toString().split("\n");
let n = Number(input[0]);
let arr1 = input[1].split(" ").map(Number);
let m = Number(input[2]);
let arr2 = input[3].split(" ").map(Number);
let result = [];

// arr1 오름차순 정렬
arr1.sort((a,b) => a-b);


// lowerBound 함수 (특정 값 이상이 처음 등장하는 위치)
function lowerBound(arr,target) {
   let start = 0;
   let end = arr.length;
   while(start< end) {
       let mid = Math.floor((start+end)/2);
       if(arr[mid]>=target){
           end = mid;
       } else {
           start = mid + 1;
        }
     }
     return start;
}

// upperBound 함수 (특정 값보다 큰 값이 처음 등장하는 위치 반환)
function upperBound(arr,target){
   let start = 0;
   let end = arr.length;
   while(start<end){
       let mid = Math.floor((start+ end) / 2);
       if(arr[mid]> target){
           end = mid;
       } else {
           start = mid + 1;
       }
   }
   return end;
}

// m 만큼 순회하면서 lower , upper 구해서 빼준 후 result 배열에 넣어줌
for(let i=0;i<m;i++){
    let lower = lowerBound(arr1, arr2[i]);
    let upper = upperBound(arr1, arr2[i]);
    result.push(upper-lower);
}
console.log(result.join(" "));