JavaScript 배열이 정렬되고 회전되었는지 확인하는 방법
카테고리
프로그래밍/소프트웨어 개발
서브카테고리
웹 개발
대상자
JavaScript 개발자(중급 이상)
- 배열 알고리즘 문제 해결에 관심 있는 개발자
- 코딩 인터뷰 준비 중인 개발자
- 알고리즘 최적화 기법 학습자
핵심 요약
- 문제 정의: 배열이 오름차순 정렬된 후 회전되었는지 확인하는 알고리즘 요구
- 핵심 접근법:
binary search
를 활용한 O(log n) 시간 복잡도 알고리즘 - 구현 핵심:
findRotationPoint()
함수를 통해 회전 지점 탐색
섹션별 세부 요약
1. 문제 정의
- 배열이 정렬되고 회전되었는지 판단
- 예: [3,4,5,1,2] → 정렬 후 회전
- 예: [1,2,3,4,5] → 정렬만 되어 있음
- 조건: 배열 요소가 중복되지 않음
2. 알고리즘 설계
- 이진 탐색 활용:
arr[mid] > arr[right]
→ 회전 지점이 오른쪽에 존재arr[mid] < arr[left]
→ 회전 지점이 왼쪽에 존재- 시간 복잡도: O(log n)
- 기본 조건 검증:
```javascript
if (arr.length < 2) return true;
if (arr[0] < arr[arr.length - 1]) return false;
```
3. 구현 세부사항
- 회전 지점 찾기:
```javascript
function findRotationPoint(arr, left, right) {
while (left < right) {
const mid = Math.floor((left + right) / 2);
if (arr[mid] > arr[right]) left = mid + 1;
else right = mid;
}
return left;
}
```
- 최종 검증:
```javascript
const pivot = findRotationPoint(arr, 0, arr.length - 1);
return isSorted(arr, pivot, arr.length - 1) && isSorted(arr, 0, pivot - 1);
```
결론
- 핵심 팁: 이진 탐색을 활용한 회전 지점 탐색으로 효율적 판단
- 주의 사항: 배열 요소 중복 시 알고리즘 오류 발생 가능
- 실무 적용: 코딩 인터뷰, 알고리즘 문제 풀이, 배열 정렬 검증 시 활용 가능