JavaScript 문제 해결: 수열에서 누락된 숫자 찾기
카테고리
프로그래밍/소프트웨어 개발
서브카테고리
웹 개발
대상자
- 중급 이상 JavaScript 개발자
- 알고리즘 문제 해결 훈련 필요자
- 문제 상황에서 효율적인 코드 작성법을 배우고자 하는 자
핵심 요약
- 수열에서 누락된 숫자를 찾는 방법
- 수열의 합 비교, 반복문 탐색, Set 자료구조 활용 등 다양한 알고리즘 적용
- 수열의 특성에 따른 처리 방식
- 산술 수열, 정렬된 수열, 중복 허용/불허용 등 조건에 따라 알고리즘 변경 필요
- Edge Case 대응
- NaN, null, 비정상적인 입력값 처리 필수 (예: if (Array.isArray(arr)))
섹션별 세부 요약
1. 문제 정의
- 목표: 주어진 수열에서 누락된 숫자(또는 숫자들의 집합)를 식별
- 예시 입력:
[1, 2, 4, 5]→ 출력:3 - 제약 조건: 수열이 정렬되었거나, 산술 수열일 수 있음
2. 주요 해결 알고리즘
- 합 비교 방법
- 수열의 기대 합(예: sum = n*(n+1)/2)과 실제 합 비교
- 시간 복잡도: O(n)
- Set 기반 탐색
- new Set(arr) 생성 후 기대 범위 내 숫자 탐색
- 시간 복잡도: O(n)
- 반복문 기반 탐색
- for 또는 while로 수열 순회하며 누락된 숫자 체크
- 시간 복잡도: O(n)
3. Edge Case 및 고려사항
- 비정상 입력 처리
- isNaN, null, undefined 값 필터링 필요
- 예: arr.filter(x => !isNaN(x))
- 중복 허용 수열 대응
- Set 또는 Map으로 중복 제거 후 처리
- 대규모 데이터 처리 최적화
- reduce 또는 Math 함수 활용 (예: Math.max(...arr))
결론
- 효율적인 알고리즘 선택: 수열의 특성(정렬 여부, 중복 허용)에 따라
Set,reduce,Math함수 선택 - Edge Case 처리 강화: 입력 검증(
Array.isArray,isNaN)과 예외 처리(try/catch) 필수 - 실무 적용 팁:
for...of반복문과Set활용으로 간결한 코드 구현 가능 - 예시 코드:
```javascript
function findMissingNumbers(arr) {
const sorted = arr.sort((a, b) => a - b);
const expected = new Set([...Array(Math.max(...arr)).keys()]);
return [...expected].filter(x => !arr.includes(x));
}
```