[백준] 1920번: 수 찾기 (실버 4) - Javascript 풀이

문제 링크

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

 

구현

<첫 답안>

const fs = require('fs');
const input = fs.readFileSync('예제.txt', 'utf8').trim().split('\n'); // 백준 경로:'/dev/stdin'

const N = parseInt(input[0]);
const arrayA = input[1].split(' ').map(Number).sort((a,b)=> a-b);
const M = parseInt(input[2]);
const arrayB = input[3].split(' ').map(Number);

const result = [];

//B의 수가 A에 존재하면 1, 아니면 0

//binary search
let start = 0;
let end = N-1;

for(const target of arrayB){
  while(start<=end){ //루프 종료 조건 : 시작인덱스>종료인덱스
    let mid = Math.floor((start + end)/2);
    let midValue = arrayA[mid];

    if(midValue>target){
      end = mid - 1;
    }
    else if(midValue<target){
      start = mid + 1;
    }
    else if(midValue === target){ //반복문 종료
      result.push(1);
      break;
    }
    else { //못찾았을때
      result.push(0);
    }
  }
}

console.log(result);

 

<문제점>

- start, end, found 를 각 target마다 초기화해야한다.

 

- target값이 없을 때 로직을 잘못 구현했다.

 else { //못찾았을때
      result.push(0);
    }

 

while 문에서 이 코드는 절대 실행되지 않는다.

target 값이 없으면 인덱스가 조정되어 while 루프가 끝날 뿐, else에 도달하지 않는다.

따라서 while문이 끝난 뒤 찾지 못한 사실을 확인하고, 0을 추가해야한다.

 

<올바른 답안>

const fs = require('fs');
const input = fs.readFileSync('예제.txt', 'utf8').trim().split('\n'); // 백준 경로:'/dev/stdin'

const N = parseInt(input[0]);
const arrayA = input[1]
  .split(' ')
  .map(Number)
  .sort((a, b) => a - b);
const M = parseInt(input[2]);
const arrayB = input[3].split(' ').map(Number);

const result = [];

//B의 수가 A에 존재하면 1, 아니면 0

//binary search

for (const target of arrayB) {
  let start = 0;
  let end = N - 1;
  let found = false;

  while (start <= end) {
    //루프 종료 조건 : 시작인덱스>종료인덱스
    let mid = Math.floor((start + end) / 2);
    let midValue = arrayA[mid];

    if (midValue > target) {
      end = mid - 1;
    } else if (midValue < target) {
      start = mid + 1;
    } else {
      //midValue === target
      result.push(1);
      found = true;
      break;
    }
  }
  if (!found) {
    result.push(0);
  }
}

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