위키득계정 ↗
기술

정렬된 배열에서 범위 개수 세기

정렬된 배열에서 범위 개수 세기기술
전제
검색 기준으로 정렬된 배열
닫힌 구간
양 끝값 포함
계산
오른쪽 경계 위치에서 왼쪽 경계 위치를 뺌
주의점
중복값과 끝값 포함 여부
정렬된 배열에서는 구간의 시작 경계와 끝 경계를 각각 찾아 값의 개수를 계산할 수 있다. 경계를 구하는 비교식에 따라 끝값 포함 여부가 달라지므로 구간 표기를 먼저 정해야 한다.

두 위치의 차이

배열이 2, 4, 4, 7, 9일 때 값이 4 이상 7 이하인 항목은 세 개다. 처음으로 4 이상이 되는 위치는 0부터 세면 1이고 처음으로 7보다 커지는 위치는 4다. 두 위치의 차이 4에서 1을 뺀 값이 개수가 된다. 항목을 하나씩 읽는 대신 원하는 구간을 감싸는 위치를 찾는 방법이다.

끝값의 포함 여부

하한 L과 상한 R을 모두 포함하면 처음으로 L 이상인 위치와 처음으로 R보다 큰 위치를 사용한다. 상한을 제외하는 구간이라면 끝 위치는 처음으로 R 이상인 곳이다. 문서에서 구간을 닫힌 구간인지 반열린 구간인지 명시하지 않으면 같은 입력으로 다른 답을 만들 수 있다.

중복과 빈 결과

동일한 값이 여러 번 있으면 어떤 한 항목을 찾는 검색만으로 개수를 알 수 없다. 중복 묶음의 양쪽 경계를 찾아야 한다. 해당 값이 전혀 없으면 두 경계가 같아져 개수가 0이 된다. 모든 값보다 작은 구간이나 큰 구간도 위치가 배열 양 끝으로 수렴하도록 처리하면 별도의 임의 보정이 줄어든다.

정렬 전제와 변경 비용

배열이 검색에 사용하는 키 순서로 정렬되어 있어야 한다. 다른 기준으로 정렬된 결과에 같은 경계 검색을 적용할 수는 없다. 검색 두 번은 일반적으로 O(log N)이지만 정렬을 처음 만드는 비용이나 배열 중간에 항목을 삽입하는 비용은 별개다. 변경이 잦다면 조회 횟수와 갱신 비용을 함께 비교한다.

잘못된 구간의 처리

L이 R보다 큰 입력에서는 빈 구간을 반환하거나 오류로 처리하는 규칙을 정한다. 경계 위치를 무조건 빼기만 하면 음수가 나올 수 있다. 또한 비교 중 데이터가 바뀌면 처음 경계를 찾았을 때와 두 번째 경계를 찾았을 때의 배열이 달라질 수 있으므로 일관된 입력을 기준으로 계산해야 한다.

관련 문서

이진 탐색의 경계 조건 / 이진 탐색 / 배열