백준 1920 : 수 찾기

문제

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

풀이

문제를 정리해보면 [4,6,5,3,2] 라는 배열을 기준으로 [4,7,6,3,2] 배열 안에 있는 각 숫자들이 기준 배열에 포함되어있는지 아닌지를 판단하면 됨

각 배열의 크기가 최대 10^5이기 때문에 최대 10^5^2까지의 시간복잡도가 나올 수 있어서 이중 반복문으로 풀 수는 없음

그래서 이분탐색 알고리즘을 사용해야 하는데, 말 그대로 배열을 이분화(쪼개서)해서 탐색하는 방법

 

예를 들어 [1,5,7,9,11] 이라는 배열이 있을 때, 9라는 숫자가 포함되었는지를 확인하고 싶다면

 

일단 시작인덱스, 끝 인덱스를 st=0,en=4로 저장해놓고, 둘의 중간값을 구해서 해당 값을 구해줌

 

여기서는 mid = 2 , arr[2] = 7이 되는데, 7은 구해야 하는 값인 9보다 작다. 이 말은 0번부터 2번까지의 값은 7보다 작은 값만 존재하기 때문에, 9를 구해야 되는 입장에서는 굳이 탐색할 필요가 없고 , 3번부터 4번까지의 값을 탐색해야 함

 

그러면 이제 st를 3으로 , end를 4로 놓고 중간값인 3번째의 값을 보면 9가 나오게 됨

 

정리해보면 시작index와 끝index를 찾고 그 중간지점의 값을 구해서, 목표 값보다 크다면 시작index는 그대로, 끝index를 중간지점-1로 바꾸기
목표 값보다 작다면, 시작index를 중간지점 +1 , 끝index는 그대로 해서 목표값이 나올때까지 반복문을 돌려주면 됨

 

만약에 포함되어있지 않은 숫자인 6를 구할 때를 살펴보면

시작=0,끝=4,중간=2 arr[2] = 7 -> 6보다 크기 때문에 5는 2번째 이상에서는 없고, 0번째와 1번째사이에 위치한다고 추측할 수 있음

시작=0,끝=1,중간=0 arr[0] = 1 -> 6보다 작기 때문에 5는 0번째 이하에는 없고, 1번째와 1번째 사이에 위치한다고 추측할 수 있음

시작=1 끝=1 중간=1 arr[1] = 5 -> 6보다 작기 때문에 5는 1번째 이하에는 없고, 2번째와 1번째 사이에 위치한다고 봐야 하는데 시작>끝일 수는 없기 때문에 시작>끝이 나온다면 그 수는 포함되어있지 않는 수가 됨

당연히 정렬 되어있는 배열에서만 사용 가능

코드

const arr = input[1].sort((a, b) => a - b);
let result = "";
for (let i of input[3]) {
  let [st, en] = [0, input[0] - 1];
  while (st <= en) {
    let mid = Math.floor((st + en) / 2);
    if (arr[mid] === i) {
      result += 1 + "\n";
      break;
    }
    if (arr[mid] < i) {
      st = mid + 1;
    }
    if (arr[mid] > i) {
      en = mid - 1;
    }
  }
  if (st > en) {
    result += 0 + "\n";
  }
}
console.log(result);