[Baekjoon] js 20551 Sort 마스터 배지훈의 후계자
문제
지훈이는 Sort 마스터다. 오랫동안 Sort 마스터 자리를 지켜온 지훈이는 이제 마스터 자리를 후계자에게 물려주려고 한다. 수많은 제자들 중에 후계자를 고르기 위해서 지훈이는 제자들에게 문제를 준비했다. 먼저 제자들에게 개의 원소를 가진 배열를 주고, 의 원소들이 오름차순으로 정렬된 배열를 만들게 한다. 그다음 개의 질문을 한다. 각 질문에는 정수 가 주어진다. 제자들은 주어진 정수가 에서 가장 먼저 등장한 위치를 출력하면 된다. 단, 가 에 존재하지 않는 경우에는 -1를 출력한다. Sort 마스터의 자리를 너무나도 물려받고 싶은 창국이를 위해 지훈이의 문제를 풀 수 있는 프로그램을 만들어 주자.
해결과정
처음에 문제를 보고 자바스크립트 내장함수인 indexOf를 사용하여 문제를 풀어봤는데 시간초과가 났었다.
indexOf는 선형 탐색을 사용하여 배열의 처음부터 끝까지 순차적으로 요소를 비교하여 주어진 값과 일치하는 첫 번째 요소의 인덱스를 찾는다. 그래서 최악의 경우 배열의 모든 요소를 확인해야 하므로 O(n)의 선형 시간 복잡도를 가지기 때문에 시간초과가 난 것이였다.
그래서 이분 탐색을 사용하여 문제를 풀어보았다. 이분 탐색은 O(log n)의 시간 복잡도를 가져 더 효율적이다. 여기서 주의해야할 점은 주어진 정수D가 B에서 가장 먼저 등장한 위치를 출력을 해야하기 때문에 Lower Bound라는 개념을 통해 문제를 풀어야한다.
Lower Bounder란?
Lower Bound는 주어진 값보다 크거나 같은 첫 번째 요소의 위치를 찾는 알고리즘으로 이는 정렬된 배열에서 특정 값 이상의 값을 갖는 첫 번째 요소의 인덱스를 찾는 것을 의미한다.
예를 들어, 배열 [1, 2, 3, 3, 3, 4, 5]에서 Lower Bound를 찾는다고 가정하면, 찾는 값이 3인 경우 Lower Bound는 2가 된다.
lowerBound코드
const lowerBound = (arr, target) => {
let left = 0;
let right = arr.length;
while (left < right) {
const mid = Math.floor((left + right) / 2);
if (arr[mid] >= target) {
right = mid;
} else {
left = mid + 1;
}
}
return arr[left] === target ? left : -1;
};함수 설명
- left와 right를 초기화하고, 이진 탐색을 시작
- 중간 값을 계산하고, 해당 값과 목표 값(target)을 비교
- 만약 중간 값이 목표 값보다 크거나 같으면, 오른쪽 범위를 줄임
- 그렇지 않으면, 왼쪽 범위를 줄임
- 이 과정을 반복하여 target 위치를 찾음
전체코드
const fs = require("fs");
const input = fs
.readFileSync("/dev/stdin")
.toString()
.trim()
.split("\n")
.map((v) => v.trim());
const lowerBound = (arr, target) => {
let left = 0;
let right = arr.length;
while (left < right) {
const mid = Math.floor((left + right) / 2);
if (arr[mid] >= target) {
right = mid;
} else {
left = mid + 1;
}
}
return arr[left] === target ? left : -1;
};
const [n, m] = input.shift().split(" ").map(Number);
let arr = [];
let result = [];
for (let i = 0; i < n; i++) {
arr.push(Number(input[i]));
}
arr = arr.sort((a, b) => a - b);
for (let i = 0; i < m; i++) {
result.push(lowerBound(arr, Number(input[i + n])));
}
console.log(result.join("\n"));