백준) 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"));