백준_암기왕_2776

암기왕

문제

연종이는 엄청난 기억력을 가지고 있다. 그래서 하루 동안 본 정수들을 모두 기억 할 수 있다. 하지만 이를 믿을 수 없는 동규는 그의 기억력을 시험해 보기로 한다. 동규는 연종을 따라 다니며, 연종이 하루 동안 본 정수들을 모두 ‘수첩1’에 적어 놓았다. 그것을 바탕으로 그가 진짜 암기왕인지 알아보기 위해, 동규는 연종에게 M개의 질문을 던졌다. 질문의 내용은 “X라는 정수를 오늘 본 적이 있는가?” 이다. 연종은 막힘없이 모두 대답을 했고, 동규는 연종이 봤다고 주장하는 수 들을 ‘수첩2’에 적어 두었다. 집에 돌아온 동규는 답이 맞는지 확인하려 하지만, 연종을 따라다니느라 너무 힘들어서 여러분에게 도움을 요청했다. 동규를 도와주기 위해 ‘수첩2’에 적혀있는 순서대로, 각각의 수에 대하여, ‘수첩1’에 있으면 1을, 없으면 0을 출력하는 프로그램을 작성해보자.

입력

첫째 줄에 테스트케이스의 개수 T가 들어온다. 다음 줄에는 ‘수첩 1’에 적어 놓은 정수의 개수 N(1 ≤ N ≤ 1,000,000)이 입력으로 들어온다. 그 다음 줄에 ‘수첩 1’에 적혀 있는 정수들이 N개 들어온다. 그 다음 줄에는 ‘수첩 2’에 적어 놓은 정수의 개수 M(1 ≤ M ≤ 1,000,000) 이 주어지고, 다음 줄에 ‘수첩 2’에 적어 놓은 정수들이 입력으로 M개 들어온다. 모든 정수들의 범위는 int 로 한다.

출력

‘수첩2’에 적혀있는 M개의 숫자 순서대로, ‘수첩1’에 있으면 1을, 없으면 0을 출력한다.

예제 입력

1
5
4 1 5 2 3
5
1 3 7 9 5

예제 출력

1
1
0
0
1

Code

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

let T = +input[0]; // 테스트케이스 개수
let line = 1;

const binarySearch = (start, end, target, arr) => {
  while (start <= end) {
    const mid = parseInt((start + end) / 2);
    if (target === arr[mid])
      return 1; // 해당 값 찾은 경우 1 리턴
    else if (target < arr[mid])
      end = mid - 1; // target이 현재 값보다 작은 경우 end값 변경
    else start = mid + 1; // target이 현재 값보다 큰 경우 start값 변경
  }
  return 0;
};

let answer = '';
while (T > 0) {
  const N = +input[line];
  const note1 = input[line + 1].split(' ').map(Number); // 수첩 1에 적힌 정수들
  note1.sort((a, b) => a - b); // 수첩1에 적힌 정수들 오름차순 정렬
  const note2 = input[line + 3].split(' ').map(Number); // 수첩 2에 적힌 정수들
  note2.forEach((note) => (answer += binarySearch(0, N, note, note1) + '\n'));
  T -= 1;
  line += 4;
}
answer = answer.trimEnd();
console.log(answer);

풀이 및 해설

• 수첩2에 적힌 정수들이 수첩1에 존재하는지 확인 ⇒ 존재하면 1, 없으면 0 출력 ⇒ JS의 includes메서드(O(n)) 이용하면 시간 복잡도가 O(NM)이 되어 비효율적임!
  
• 이분 탐색 이용!
  1. 수첩 1의 정수들 오름차순 정렬
  2. 수첩2의 정수를 하나씩 순회하면서 이분탐색 수행
     1. mid값구하여 수첩2의 현재 정수가 수첩1의 mid인덱스 위치의 정수보다 작으면 end를 mid-1로 변경
     2. mid값보다 크다면 start를 mid+1로 변경
     3. mid값과 일치한다면 1출력
• 해시테이블 집합 이용!
  1. 수첩 1의 정수들을 집합 배열에 넣기
  2. 수첩2 정수들을 순회하면서 수첩1에 존재하는지 확인 ⇒ O(1)

⇒ 이분탐색보다 해시테이블 이용하면 시간이 절반 정도 단축됨!