특정 값의 출현 횟수 세기

목표: 배열에서 특정 값이 몇 번 나오는지 세어본다.

가장 간단한 방법은 배열의 처음부터 끝까지 선형 탐색을 하며 해당 값이 나올 때마다 카운트를 증가시키는 것이다. 이 방법은 O(n) 시간 복잡도를 가진다.

하지만 배열이 정렬되어 있다면 이진 탐색을 변형해 O(log n) 시간에 해결할 수 있다.

다음과 같은 배열이 있다고 가정한다:

[ 0, 1, 1, 3, 3, 3, 3, 6, 8, 10, 11, 11 ]

여기서 값 3이 몇 번 나오는지 알고 싶다면, 먼저 일반적인 이진 탐색으로 3을 찾는다. 이때 반환되는 인덱스는 다음 네 가지 중 하나일 것이다:

[ 0, 1, 1, 3, 3, 3, 3, 6, 8, 10, 11, 11 ]
           *  *  *  *

하지만 이 방법으로는 다른 3들이 어디에 있는지 알 수 없다. 다른 3들을 찾기 위해선 왼쪽과 오른쪽으로 선형 탐색을 해야 한다. 대부분의 경우 이 방법도 충분히 빠르지만, 최악의 경우(배열이 모두 3으로 구성된 경우) 여전히 O(n) 시간이 걸린다.

더 효율적인 방법은 두 번의 이진 탐색을 사용해 3이 시작되는 지점(왼쪽 경계)과 끝나는 지점(오른쪽 경계)을 찾는 것이다.

코드는 다음과 같다:

func countOccurrences<T: Comparable>(of key: T, in array: [T]) -> Int {
  var leftBoundary: Int {
    var low = 0
    var high = array.count
    while low < high {
      let midIndex = low + (high - low)/2
      if a[midIndex] < key {
        low = midIndex + 1
      } else {
        high = midIndex
      }
    }
    return low
  }

  var rightBoundary: Int {
    var low = 0
    var high = array.count
    while low < high {
      let midIndex = low + (high - low)/2
      if a[midIndex] > key {
        high = midIndex
      } else {
        low = midIndex + 1
      }
    }
    return low
  }

  return rightBoundary - leftBoundary
}

leftBoundary와 rightBoundary 변수는 이진 탐색 알고리즘과 매우 유사하다. 차이점은 검색 키를 찾았을 때 멈추지 않고 계속 진행한다는 것이다. 또한 T 타입이 Comparable을 준수하도록 제약을 걸어 문자열, 정수 등 다양한 타입에 이 알고리즘을 적용할 수 있다.

이 알고리즘을 테스트하려면 코드를 플레이그라운드에 복사한 후 다음을 실행한다:

let a = [ 0, 1, 1, 3, 3, 3, 3, 6, 8, 10, 11, 11 ]

countOccurrences(of: 3, in: a)  // 4를 반환

주의: 직접 배열을 사용할 땐 반드시 정렬되어 있는지 확인한다!

예제를 따라가 보자. 배열은 다음과 같다:

[ 0, 1, 1, 3, 3, 3, 3, 6, 8, 10, 11, 11 ]

왼쪽 경계를 찾기 위해 low = 0, high = 12로 시작한다. 첫 번째 중간 인덱스는 6이다:

[ 0, 1, 1, 3, 3, 3, 3, 6, 8, 10, 11, 11 ]
                    *

일반적인 이진 탐색이라면 여기서 끝이지만, 이 알고리즘은 값 3이 존재하는지 여부뿐만 아니라 처음 나오는 위치를 찾는다.

이진 탐색과 같은 원리를 따르므로 배열의 오른쪽 절반을 무시하고 새로운 중간 인덱스를 계산한다:

[ 0, 1, 1, 3, 3, 3 | x, x, x, x, x, x ]
           *

다시 3에 도달했고, 이번엔 첫 번째 3이다. 하지만 알고리즘은 이를 알지 못하므로 배열을 다시 나눈다:

[ 0, 1, 1 | x, x, x | x, x, x, x, x, x ]
     *

아직 끝나지 않았다. 다시 나누되 이번엔 오른쪽 절반을 사용한다:

[ x, x | 1 | x, x, x | x, x, x, x, x, x ]
         *

배열을 더 이상 나눌 수 없으므로 왼쪽 경계를 찾았다. 인덱스는 3이다.

이제 오른쪽 경계를 찾는다. 과정은 매우 유사하므로 주요 단계만 보여준다:

[ 0, 1, 1, 3, 3, 3, 3, 6, 8, 10, 11, 11 ]
                    *

[ x, x, x, x, x, x, x | 6, 8, 10, 11, 11 ]
                              *

[ x, x, x, x, x, x, x | 6, 8, | x, x, x ]
                           *

[ x, x, x, x, x, x, x | 6 | x | x, x, x ]
                        *

오른쪽 경계는 인덱스 7이다. 두 경계의 차이는 7 - 3 = 4이므로, 숫자 3은 이 배열에서 네 번 나온다.

각 이진 탐색에 4단계가 걸렸으므로 총 8단계가 소요되었다. 12개의 항목으로 구성된 배열에선 큰 차이가 없지만, 배열이 커질수록 이 알고리즘은 더 효율적이다. 1,000,000개의 항목으로 구성된 정렬된 배열에선 특정 값의 출현 횟수를 세는 데 2 x 20 = 40단계만 걸린다.

찾는 값이 배열에 없는 경우, rightBoundary와 leftBoundary는 같은 값을 반환하므로 차이는 0이 된다.

이 예제는 기본 이진 탐색을 변형해 다른 알고리즘 문제를 해결할 수 있는 방법을 보여준다. 물론 배열이 정렬되어 있어야 한다는 전제가 필요하다.

Swift Algorithm Club의 Matthijs Hollemans가 작성함