앞쪽이 모두 작거나 같은 분할 지점 개수
자바스크립트 코딩테스트 문제로 prefix-suffix 주제를 연습해보세요. 난이도는 easy이며, 브라우저에서 바로 JavaScript로 풀이를 실행할 수 있습니다.
배열을 둘로 나눌 수 있는 지점 중, 왼쪽의 모든 값이 오른쪽의 모든 값보다 작거나 같은 지점의 개수를 구하는 문제입니다.
문제 설명
정수 배열 nums가 주어집니다.
배열의 어떤 위치에서 왼쪽 부분과 오른쪽 부분으로 나눌 수 있습니다. 이때 왼쪽 부분에 있는 모든 값이 오른쪽 부분에 있는 모든 값보다 작거나 같다면 그 위치를 안정적인 분할 지점이라고 합니다.
안정적인 분할 지점의 개수를 반환하는 countStableSplitPoints 함수를 작성하세요.
분할은 반드시 원소와 원소 사이에서만 할 수 있으므로, 왼쪽과 오른쪽 부분이 모두 비어 있지 않아야 합니다.
제한사항
nums의 길이는1이상100,000이하입니다.nums의 각 원소는-1,000,000이상1,000,000이하의 정수입니다.- 길이가
1이면 나눌 수 있는 지점이 없으므로0을 반환합니다.
예시
- 입력:
[1, 3, 5, 4, 6, 8]→ 출력:2- 가능한 안정 분할은 인덱스 기준으로
1과3뒤입니다. [1, 3, 5] | [4, 6, 8]은 왼쪽 최대값이5, 오른쪽 최소값이4라서 실패합니다.[1, 3] | [5, 4, 6, 8]은 왼쪽 최대값3, 오른쪽 최소값4라서 성공합니다.[1, 3, 5, 4] | [6, 8]은 왼쪽 최대값5, 오른쪽 최소값6이라서 성공합니다.
- 가능한 안정 분할은 인덱스 기준으로
- 입력:
[2, 2, 2]→ 출력:2- 같은 값은 허용되므로 두 분할 모두 가능합니다.
- 입력:
[5, 4, 3, 2]→ 출력:0- 어느 위치에서 나눠도 왼쪽에 더 큰 값이 남습니다.
힌트
- 어떤 분할이 가능한지 확인할 때 왼쪽 전체의 최댓값만 알면 충분합니다.
- 오른쪽 전체의 최솟값도 빠르게 알 수 있으면 매 위치를 바로 판정할 수 있습니다.
- 왼쪽에서 한 번, 오른쪽에서 한 번 미리 정보를 만들어 보세요.
해설
분할선이 i 뒤에 있다고 해 봅시다.
그러면 왼쪽은 nums[0..i], 오른쪽은 nums[i+1..n-1]입니다.
이 분할이 유효하려면
- 왼쪽의 가장 큰 값
leftMax - 오른쪽의 가장 작은 값
rightMin
이 두 값만 비교하면 됩니다.
즉, leftMax <= rightMin이면 그 분할은 안정적입니다.
이를 빠르게 처리하려면 다음 두 배열을 만듭니다.
prefixMax[i]:0번부터i번까지의 최댓값suffixMin[i]:i번부터 마지막까지의 최솟값
그다음 i = 0부터 n - 2까지 보면서
- 왼쪽 최댓값은
prefixMax[i] - 오른쪽 최솟값은
suffixMin[i + 1]
을 비교해 prefixMax[i] <= suffixMin[i + 1]인 횟수를 세면 됩니다.
이 방식은 배열을 몇 번 선형으로만 순회하므로 시간 복잡도는 O(n)이고, 추가 공간은 O(n)입니다.
코드 작성
starter code를 바탕으로 함수를 완성한 뒤 예제 테스트를 실행해보세요.
커스텀 테스트
함수 인자를 JSON 배열 형태로 입력하세요. 예: [3, 5], [[1, 2, 3]]
실행 결과
아직 실행하지 않았습니다.
댓글
문제 풀이 아이디어, 질문, 반례를 자유롭게 나눠보세요.