백준 - 10816 숫자카드2

문제

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

입력

• 첫째 줄
  • 상근이가 가지고 있는 숫자 카드의 개수 N
• 둘째 줄
  • 상근이가 가지고 있는 숫자 카드
• 셋째 줄
  • 상근이의 카드와 비교할 숫자 카드 개수 M
• 넷째 줄
  • 상근이의 카드와 비교할 숫자 카드

제한 조건

• 1 ≤ N, M ≤ 500,000
• 10,000,000 ≤ 숫자 카드에 적혀있는 수 ≤ 10,000,000
• 상근이 숫자카드는 중복 됨

예시

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

// NOTE: 출력
3 0 0 1 2 0 0 2

해결

이 문제는 2가지 해결 방법이 있다.

1. 이분탐색
2. Map 객체

문제가 나온 시점에는 Map 객체가 없었나??
풀면서 Map 객체 혹은 heap의 탐색 속도가 빠르다는걸 체감했다.

Map을 쓰니까, 속도가 3배정도 빨라졌다.

문제가 원하는 것

이분탐색은 리스트 정렬, start, end, mid 네 가지가 정리되어야 한다!
이 문제는 target을 찾고, 리스트에 target이 있으면 갯수를 없으면 0을 반환하면 된다!

해결(이분탐색)

에러난 방법

• 메모리 초과
  • item이 [카드 숫자, 갯수]인 list를 만드는 과정에서 reduce를 사용
  • 완전 탐색하면서 acc에 새로운 배열을 선언해서 메모리 초과 에러가 발생
• 해결
  • 빈 배열을 만들고
  • for문을 돌면서 조건에 맞으면 arr.push([카드 숫자, 갯수]) 한다.

탐색할 리스트

상근이가 가진 카드를 개조한 list를 탐색할거다.

• item = [카드 숫자, 갯수]
• 이 리스트를 이분 탐색할 때
  • target = list[index][0]
  • count = list[index][1]
  • 구조분해 할당해서 사용할 예정
• 개조과정
  1. input data를 sort 한다.
  2. 새 배열을 만들고 초기값을 넣는다.
     • 초기 값 = [sortedArr의 첫번째 요소, 1]
  3. sort된 배열을 2번째 값부터 개조 시작
     • 반복문 범위는 1 ~ sortedArr.length
     • list의 마지막 요소를 pop
       • before와 count를 추출
       • sortedArr[i]는 current라 정의
     • before == current인 경우
       • list.push([before, count + 1])
     • before != current인 경우
       • _list.push([before, count], [current, 1]);
       • 아까 pop으로 before 값 빼서 그럼

const getList = (arr) => {
    const _sorted_arr = arr.trim().split(' ').sort((a, b) => +a - +b);
    const _list = [[+_sorted_arr[0], 1]];
    
    for (let i = 1; i < _sorted_arr.length; i++) {
        const [_before, _count] = _list.pop();
        const _cur = +_sorted_arr[i];
        
        if (_before == _cur) {
            _list.push([_before, _count + 1]);
            continue;
        }
        
        _list.push([_before, _count], [_cur, 1]);
    }
    
    return _list;
};

탐색(재귀)

• 첫 탐색 범위를 0 ~ (개조한 list.length - 1)로 설정한다.
• mid를 구하고 target과 비교한다.

  • 구조분해 할당으로 target과 비교할 card 값을 추출

    const _mid = Math.floor((start + end) / 2);
    const [_card, _count] = list[_mid];

  • start > end 인 경우

    • 상근이가 가지고 있지 않다는 의미로, return 0

  • target == card인 경우

    • 상근이가 가지고 있다는 의미로, return count

  • target > card인 경우

    • 중간 값이 target보다 작으니까, 시작 값을 높이면서 탐색범위를 줄여야 한다.
    • start = mid + 1

  • target < card인 경우

    • 중간 값이 target보다 크니까, 끝 값을 줄이면서 탐색범위를 줄여야 한다.
    • end = mid - 1

결과 출력

• binarySearch로 매핑한 값을 join하여 출력한다.

전체 코드

// NOTE: inputs
let [, _inputs, , _cards] = require('fs')
    .readFileSync('dev/stdin')
    .toString()
    .trim()
    .split(/\n/);

// NOTE: solution
const binarySearch = (target, list, start, end) => {
    if (start > end) return 0;
    
    const _mid = Math.floor((start + end) / 2);
    const [_card, _count] = list[_mid];
    
    if (target == _card) return _count;
    if (target > _card) return binarySearch(target, list, _mid + 1, end);
    return binarySearch(target, list, start, _mid - 1);
}

const getList = (arr) => {
    const _sorted_arr = arr.trim().split(' ').sort((a, b) => +a - +b);
    const _list = [[+_sorted_arr[0], 1]];
    
    for (let i = 1; i < _sorted_arr.length; i++) {
        const [_before, _count] = _list.pop();
        const _cur = +_sorted_arr[i];
        
        if (_before == _cur) {
            _list.push([_before, _count + 1]);
            continue;
        }
        
        _list.push([_before, _count], [_cur, 1]);
    }
    
    return _list;
};

const _list = getList(_inputs);
const _end = _list.length - 1;
const _result = _cards.trim().split(' ').map(v => binarySearch(v, _list, 0, _end)).join(' ');
console.log(_result);

해결(Map 객체)

search할 Map 객체 생성

• 상근이가 가지고 있는 카드를 완전탐색하기 전에, map 객체 생성
• 완전 탐색
  • key = card
  • value = count

map으로 결과값 매핑

• searchMap에 카드가 있으면 값으로 대체
• 없으면 0으로 대체

전체 코드

// NOTE: inputs
let [, _inputs, , _cards] = require('fs')
    .readFileSync('dev/stdin')
    .toString()
    .trim()
    .split(/\n/);

// NOTE: solution
const splitString = (str) => str.trim().split(' ');

const getMap = (input) => {
    const _map = new Map();
    
    for (let _card of splitString(input)) {
        let _count = _map.has(_card) ? _map.get(_card) : 0;
        _map.set(_card, _count + 1);
    }
    
    return _map;
};

const _searchMap = getMap(_inputs);
const _result = splitString(_cards)
    .map(v => _searchMap.has(v) ? _searchMap.get(v) : 0)
    .join(' ');
console.log(_result);