[JS] 백준 1920번 수 찾기

 

출처

백준 온라인 저지

https://www.acmicpc.net/problem/1920

1920번: 수 찾기

 

문제

N개의 정수 A [1], A [2], …, A [N]이 주어져 있을 때, 이 안에 X라는 정수가 존재하는지 알아내는 프로그램을 작성하시오.

 

첫째 줄에 자연수 N(1 ≤ N ≤ 100,000)이 주어진다. 다음 줄에는 N개의 정수 A [1], A [2], …, A [N]이 주어진다. 다음 줄에는 M(1 ≤ M ≤ 100,000)이 주어진다. 다음 줄에는 M개의 수들이 주어지는데, 이 수들이 A안에 존재하는지 알아내면 된다. 모든 정수의 범위는 -231 보다 크거나 같고 231보다 작다.

풀이

넷째 줄의 입력값들을 둘째 줄의 입력값에서 찾아서 존재 여부를 출력하면 되는 문제입니다.

 

이제 값을 찾기만 하면 되지만 일반적인 방법으로는 N과 M의 경우가 100,000개가 나올 시 최악으로 경우의 수를 일일이 모두 찾아야 할 수도 있습니다.

 

해당 풀이는 이분 탐색 방법을 사용하였습니다.

 

이분 탐색 방법에서 가장 중요한 정렬을 시켜주고 넷째 줄에 있는 값을 반복문을 돌려 탐색해 줍니다.

탐색을 할 때 중요한 게 범위인데 N에서 값을 찾아 줄 것이기 때문에 M의 길이가 아닌 N의 길이로 시작하게 됩니다.

 

완료되어 더 이상 탐색하지 못할 경우 left와 right의 값은 각 줄거나 커지게 되고 그로 인해 left의 값이 right의 값보다 더 커지게 됩니다.

 

두 번째 줄에 있는 리스트 중에 탐색할 값이 존재하면 1을 반환 없을 시 0을 반환해주며 모든 결과를 줄 바꿈 시켜 출력해줍니다.

 

코드

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

const [N, A, M, B] = input.map(v => v.split(" ").map(x => Number(x)));

A.sort((a, b) => a - b);

// 이분 탐색
const binarySearch = (list, target, left, right, mid) => {
  mid = Math.floor((left + right) / 2);

  if (right < left) {
    return list[mid] == target ? 1 : 0;
  }

  if (list[mid] > target) {
    right = mid - 1;
  } else {
    left = mid + 1;
  }

  return binarySearch(list, target, left, right, mid);
}

const result = B.map(v => binarySearch(A, v, 0, A.length - 1, 0));

console.log(result.join("\n"));

재귀를 이용해 풀이를 했으며 while문을 이용한 풀이가 더 접근하기 쉬울 것 같습니다.

 

 

다른 방식

Set 객체에 있는 has 메서드를 사용하는 방법도 있습니다.

 

has 메서드는 해당 Set 객체에 값이 존재 여부를 반환합니다.

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

const [N, A, M, B] = input.map(v => v.split(" "));

const array = new Set(A);

const result = B.map(v => array.has(v) ? 1 : 0);

console.log(result.join("\n"));

 

참고자료

https://gurtn.tistory.com/94

[JS] 이진 탐색(이분 탐색)