특수 배열(Special Array)이란?
어떤 배열에 양의 정수 num이 존재해서, 배열 안에서 num 이상인 요소의 개수가 정확히 num개가 되는 경우, 그 배열을 '특수 배열'이라고 부릅니다.
여기서 중요한 점은 num이 반드시 배열의 요소일 필요는 없다는 것입니다. 조건을 만족하는 수가 존재하기만 하면 충분합니다.
예제로 이해하기
const arr = [2, 1, 5, 2, 7, 9];
위 배열을 자세히 살펴보면, num = 3일 때 3 이상인 요소는 5, 7, 9로 정확히 3개입니다.
흥미롭게도 3 자체는 배열에 속해 있지 않지만, 이는 전혀 문제가 되지 않습니다. 조건을 만족하는 수가 존재하기만 하면 되기 때문입니다. 따라서 이 배열은 num = 3을 기준으로 하는 특수 배열입니다.
문제 정의
숫자 배열을 입력받는 자바스크립트 함수를 작성해야 합니다. 이 함수는 배열이 특수 배열이라면 그 기준이 되는 수를 반환하고, 특수 배열이 아니라면 -1을 반환해야 합니다.
구현 코드
접근 방식은 다음과 같습니다.
- 원본 배열을 보호하기 위해 복사한 뒤 오름차순으로 정렬합니다.
- 후보 값(index)을 1부터 배열의 최댓값까지 하나씩 늘려 가며 검사합니다.
- 각 후보 값마다 배열에서 그 값 이상인 요소의 개수를 셉니다.
- 개수가 후보 값과 일치하면 해당 값을 반환하고, 끝까지 일치하는 값이 없으면 -1을 반환합니다.
const arr = [2, 1, 5, 2, 7, 9];
const findSpecialArray = (array = []) => {
const arr = array.slice().sort((a, b) => a - b);
let index = 1;
const { length } = arr;
while(index <= arr[length-1]){
let num = 0;
for(let i=0; i<length; i++){
if(arr[i] >= index){
num++;
}
};
if(num === index){ return index; };
index++;
};
return -1;
};
console.log(findSpecialArray(arr));
코드 설명
- array.slice(): 원본 배열이 변경되지 않도록 복사본을 만듭니다.
- sort((a, b) => a - b): 숫자 오름차순 정렬을 수행합니다. 자바스크립트의 기본 sort는 문자열 기준으로 동작하므로 비교 함수를 반드시 전달해야 합니다.
- while 루프: 후보 값 index를 1부터 배열의 최댓값(arr[length-1])까지 순회합니다.
- 내부 for 루프: index 이상인 요소의 개수를 세어 num에 저장합니다.
- 조건 검사: num === index가 성립하면 그 값이 곧 특수 숫자이므로 즉시 반환합니다.
실행 결과
위 코드를 실행하면 다음과 같은 결과가 출력됩니다.
3
배열 [2, 1, 5, 2, 7, 9]에서 3 이상인 요소는 5, 7, 9로 정확히 3개이므로, 함수는 특수 숫자 3을 반환합니다.
성능 개선 힌트
현재 구현은 이중 반복문 구조라 시간 복잡도가 O(n²)입니다. 배열이 이미 정렬되어 있으므로 이진 탐색을 활용해 'index 이상인 첫 번째 위치'를 찾으면 개수 세기를 O(log n)으로 줄일 수 있고, 전체 성능을 O(n log n)까지 개선할 수 있습니다.