[백준 1920] 수 찾기
February 12, 2023
문제
https://www.acmicpc.net/problem/1920
아이디어
- 특정 값이 존재하는지 확인할 대상 배열을 오름차순으로 정렬한다.
-
문제 배열을 순회하면서 이진 탐색을 통해 해당 값들이 존재하는지를 확인한다.
- start를 첫 번째 인덱스, end를 마지막 인덱스로 시작한다.
-
start가 end보다 커지기 전까지 아래를 반복한다.
- mid를 (start + end) / 2로 설정한다.
- mid 인덱스에 존재하는 값이 찾으려는 값이 맞다면 1을 반환한다.
- 찾으려는 값이 mid 인덱스에 있는 값보다 작다면, end 값을 mid - 1로 설정한다.
- 찾으려는 값이 mid 인덱스에 있는 값보다 크다면, start 값을 mid + 1로 설정한다.
- 값을 찾지 못했다면 0을 반환한다.
소스코드
// 입력 정제
const INPUT_NAME = "i1.txt";
const filePath = process.platform === "linux" ? "/dev/stdin" : `./${__dirname.split('\\').pop()}/${INPUT_NAME}`;
const input = require("fs").readFileSync(filePath).toString().trim().split("\n").map(item => item.trim());
const n = Number(input[0]);
const origin = input[1].split(" ").map(e => Number(e)).sort((a, b) => a - b);
const m = Number(input[1]);
const questions = input[3].split(" ").map(e => Number(e));
// 문제
function check(value) {
let start = 0;
let end = n - 1;
while (start <= end) {
let mid = Math.floor((start + end) / 2);
if (origin[mid] === value) return 1;
else if (value < origin[mid]) end = mid - 1;
else start = mid + 1;
}
return 0;
}
function solution() {
const result = [];
questions.forEach(q => result.push(check(q)));
console.log(result.join("\n"));
}
// 실행
solution();