백준) 1920 - 수 찾기 JS

📌 문제 링크

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

---

📌 문제 탐색하기

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

시간복잡도

• O(n+m)
  • n은 nArr 의 요소 개수
  • m은 mArr 의 요소 개수

---

📌 코드 설계하기

1. 입력값을 구조 분해 할당해줍니다.
2. 대상이 되는 것을 숫자 타입으로 변환하여 Set객체에 넣어줍니다.
3. 순회해야하는 것도 숫자 타입으로 변환하여 배열로 만들어줍니다.
4. 순회할 배열을 돌며 Set에 해당 요소가 있는지 확인하며 있으면 1 을 없으면 0 을 출력합니다.

---

📌 시도 회차 수정 사항 (Optional)

1회차

• includes()를 사용했더니 시간초과로 틀렸다.

const fs = require("fs");
const filePath =
  process.platform === "linux" ? "/dev/stdin" : __dirname + "/input.txt";
const input = fs.readFileSync(filePath).toString().trim().split("\n");

const [n, nArr, m, mArr] = input;
const numNArr = nArr.split(" ").map(Number);
const numMArr = mArr.split(" ").map(Number);
for (const x of numMArr) {
  console.log(numNArr.includes(x) ? 1 : 0);
}

---

📌 정답 코드

const fs = require("fs");
const filePath =
  process.platform === "linux" ? "/dev/stdin" : __dirname + "/input.txt";
const input = fs.readFileSync(filePath).toString().trim().split("\n");

const [n, nArr, m, mArr] = input;
const nSet = new Set(nArr.split(" ").map(Number));
const numMArr = mArr.split(" ").map(Number);
const answer = [];
for (const x of numMArr) {
  answer.push(nSet.has(x) ? 1 : 0);
}
console.log(answer.join("\n"));

---

이분탐색으로 푼 풀이

//https://www.acmicpc.net/problem/1920
export {};

const fs = require("fs");
const filePath =
  process.platform === "linux" ? "/dev/stdin" : __dirname + "/input1.txt";
const input = fs.readFileSync(filePath).toString().trim().split("\n");

const N = input[1]
  .split(" ")
  .map(Number)
  .sort((a: number, b: number) => a - b);
const M = input[3].split(" ").map(Number);

const binarySearch = (arr: number[], target: number) => {
  let left = 0;
  let right = arr.length - 1;

  while (left <= right) {
    const mid = Math.floor((left + right) / 2);

    if (arr[mid] === target) return true; // 값을 찾은 경우
    else if (arr[mid] < target) left = mid + 1; // 오른쪽 부분 탐색
    else right = mid - 1; // 왼쪽 부분 탐색
  }

  return false; // 값을 찾지 못한 경우
};

// M의 각 값을 N에서 탐색
const result = M.map((x: number) => (binarySearch(N, x) ? 1 : 0));
console.log(result.join("\n"));