배열을 정렬하려면 손봐야 할 가장 짧은 구간
자바스크립트 코딩테스트 문제로 sorting 주제를 연습해보세요. 난이도는 medium이며, 브라우저에서 바로 JavaScript로 풀이를 실행할 수 있습니다.
정수 배열 nums가 주어질 때, 그 구간만 오름차순으로 정렬하면 배열 전체가 오름차순이 되도록 만드는 가장 짧은 연속 구간의 길이를 반환하는 solution 함수를 작성하세요.
제한사항
1 <= nums.length <= 100000-1000000000 <= nums[i] <= 1000000000- 오름차순은 앞의 값이 뒤의 값보다 크지 않은 상태를 뜻합니다.
- 이미 전체 배열이 오름차순이라면
0을 반환합니다. - 반드시 연속된 하나의 구간만 선택한다고 가정합니다.
예시
- 입력:
[1, 2, 6, 4, 5, 7, 8]→ 출력:3 - 입력:
[1, 2, 3, 4, 5]→ 출력:0 - 입력:
[1, 3, 2, 2, 2]→ 출력:4
힌트
- 단순히 처음으로 어긋난 위치와 마지막으로 어긋난 위치만 찾으면 부족할 수 있습니다.
- 왼쪽에서 보면서 지금까지의 최댓값보다 작은 수가 나오면, 그 지점은 정렬이 필요한 오른쪽 경계 후보입니다.
- 오른쪽에서 보면서 지금까지의 최솟값보다 큰 수가 나오면, 그 지점은 정렬이 필요한 왼쪽 경계 후보입니다.
해설
이 문제는 어떤 구간을 정렬해야 전체 배열이 오름차순이 되는지 찾는 문제입니다.
가장 쉬운 방법은 배열을 정렬한 복사본과 원본을 비교해서 처음/마지막으로 다른 위치를 찾는 것입니다. 하지만 이 문제에서는 배열의 흐름을 읽으며 경계를 잡는 방식을 익히는 것이 더 중요합니다.
1) 오른쪽 경계 찾기
왼쪽에서 오른쪽으로 이동하면서 지금까지 본 값 중 최댓값을 maxSeen으로 유지합니다.
- 현재 값이
maxSeen보다 크거나 같다면 아직 오름차순 흐름이 유지됩니다. - 현재 값이
maxSeen보다 작다면, 이 값은 앞쪽의 더 큰 값보다 뒤에 와 있으므로 정렬이 필요한 구간 안에 포함되어야 합니다. - 따라서 이런 위치를 만날 때마다 오른쪽 경계
right를 현재 인덱스로 갱신합니다.
예를 들어 [1, 2, 6, 4, 5, 7, 8]에서 4와 5는 앞에서 본 최댓값 6보다 작으므로, 최소한 그 지점들까지는 정렬해야 합니다.
2) 왼쪽 경계 찾기
이번에는 오른쪽에서 왼쪽으로 이동하면서 지금까지 본 값 중 최솟값을 minSeen으로 유지합니다.
- 현재 값이
minSeen보다 작거나 같다면 뒤쪽과의 순서가 맞습니다. - 현재 값이
minSeen보다 크다면, 이 값은 뒤쪽의 더 작은 값보다 앞에 와 있으므로 정렬이 필요한 구간 안에 포함되어야 합니다. - 따라서 이런 위치를 만날 때마다 왼쪽 경계
left를 현재 인덱스로 갱신합니다.
3) 정답 계산
- 한 번도 어긋난 위치가 없었다면 이미 정렬된 배열이므로
0입니다. - 그렇지 않다면 정답은
right - left + 1입니다.
4) 왜 이 방식이 유효한가?
배열이 오름차순이 되려면, 중간에 잘못 끼어든 큰 값과 작은 값을 모두 포함하는 구간을 정렬해야 합니다.
- 왼쪽 스캔은 뒤늦게 발견된 작은 값들 때문에 어디까지 정렬이 필요한지 알려 줍니다.
- 오른쪽 스캔은 앞에 너무 일찍 나온 큰 값들 때문에 어디서부터 정렬이 필요한지 알려 줍니다.
두 경계를 합치면, 전체 배열을 바로잡기 위해 필요한 최소 연속 구간을 얻을 수 있습니다.
이 방식은 배열을 두 번만 훑으므로 시간 복잡도는 O(n)이고, 추가 메모리는 O(1)입니다. 정렬 비교 방식보다 알고리즘 감각을 더 잘 훈련할 수 있는 대표적인 문제입니다.
코드 작성
starter code를 바탕으로 함수를 완성한 뒤 예제 테스트를 실행해보세요.
커스텀 테스트
함수 인자를 JSON 배열 형태로 입력하세요. 예: [3, 5], [[1, 2, 3]]
실행 결과
아직 실행하지 않았습니다.
댓글
문제 풀이 아이디어, 질문, 반례를 자유롭게 나눠보세요.