최소값/최대값 선택

목표: 정렬되지 않은 배열에서 최소값 또는 최대값을 찾는다.

최대값 또는 최대값

제네릭 객체로 이루어진 배열이 있다. 모든 객체를 순회하면서 현재까지의 최소값 또는 최대값을 추적한다.

예제

정렬되지 않은 리스트 [ 8, 3, 9, 4, 6 ]에서 최댓값을 찾아보자.

먼저 첫 번째 숫자인 8을 선택하고, 이를 현재까지의 최댓값으로 저장한다.

리스트에서 다음 숫자 3을 선택하고, 현재 최댓값과 비교한다. 3은 8보다 작으므로 최댓값은 여전히 8이다.

다음 숫자 9를 선택하고, 현재 최댓값과 비교한다. 9는 8보다 크므로 최댓값을 9로 업데이트한다.

리스트의 모든 요소를 처리할 때까지 이 과정을 반복한다.

코드

Swift로 간단하게 구현한 예제는 다음과 같다:

func minimum<T: Comparable>(_ array: [T]) -> T? {
  guard var minimum = array.first else {
    return nil
  }

  for element in array.dropFirst() {
    minimum = element < minimum ? element : minimum
  }
  return minimum
}

func maximum<T: Comparable>(_ array: [T]) -> T? {
  guard var maximum = array.first else {
    return nil
  }

  for element in array.dropFirst() {
    maximum = element > maximum ? element : maximum
  }
  return maximum
}

이 코드를 플레이그라운드에 넣고 다음과 같이 테스트할 수 있다:

let array = [ 8, 3, 9, 4, 6 ]
minimum(array)   // 3 반환
maximum(array)   // 9 반환

Swift 표준 라이브러리에서

Swift 라이브러리는 이미 SequenceType에 대한 확장을 포함하고 있다. 이 확장은 시퀀스에서 최소/최대 엘리먼트를 반환한다.

let array = [ 8, 3, 9, 4, 6 ]
array.minElement()   // 3을 반환
array.maxElement()   // 9를 반환

let array = [ 8, 3, 9, 4, 6 ]
//swift3
array.min()   // 3을 반환
array.max()   // 9를 반환

최대값과 최소값 찾기

배열에 포함된 최대값과 최소값을 찾으면서 비교 횟수를 최소화하려면, 각 요소를 쌍으로 비교하는 방식을 사용할 수 있다.

예제

정렬되지 않은 리스트 [ 8, 3, 9, 6, 4 ]에서 최솟값과 최댓값을 찾아보자.

첫 번째 숫자 8을 선택하고, 이를 현재 최솟값과 최댓값으로 저장한다.

리스트의 항목 수가 홀수이므로 8을 리스트에서 제거하고, 남은 쌍은 [ 3, 9 ]와 [ 6, 4 ]가 된다.

다음 숫자 쌍 [ 3, 9 ]를 선택한다. 이 두 숫자 중 3이 더 작으므로, 3을 현재 최솟값 8과 비교하고, 9를 현재 최댓값 8과 비교한다. 3은 8보다 작으므로 새로운 최솟값은 3이 된다. 9는 8보다 크므로 새로운 최댓값은 9가 된다.

다음 숫자 쌍 [ 6, 4 ]를 선택한다. 여기서 4가 더 작으므로, 4를 현재 최솟값 3과 비교하고, 6을 현재 최댓값 9와 비교한다. 4는 3보다 크므로 최솟값은 변경되지 않는다. 6은 9보다 작으므로 최댓값도 변경되지 않는다.

결과적으로 최솟값은 3이고 최댓값은 9가 된다.

코드 설명

다음은 Swift로 구현한 간단한 예제다:

func minimumMaximum<T: Comparable>(_ array: [T]) -> (minimum: T, maximum: T)? {
  guard var minimum = array.first else {
    return nil
  }
  var maximum = minimum

  // 'array'의 요소 개수가 홀수일 경우, 'minimum' 또는 'maximum'이 남은 요소를 처리하도록 함
  let start = array.count % 2 // 홀수일 경우 1, 첫 번째 요소를 건너뜀
  for i in stride(from: start, to: array.count, by: 2) {
    let pair = (array[i], array[i+1])

    if pair.0 > pair.1 {
      if pair.0 > maximum {
        maximum = pair.0
      }
      if pair.1 < minimum {
        minimum = pair.1
      }
    } else {
      if pair.1 > maximum {
        maximum = pair.1
      }
      if pair.0 < minimum {
        minimum = pair.0
      }
    }
  }

  return (minimum, maximum)
}

이 코드를 플레이그라운드에 넣고 다음과 같이 테스트한다:

let result = minimumMaximum(array)!
result.minimum   // 3을 반환
result.maximum   // 9를 반환

요소를 쌍으로 묶어 각 쌍의 최댓값과 최솟값을 현재까지의 최솟값과 최댓값과 비교함으로써, 2개의 요소마다 3번의 비교만 수행하도록 최적화했다.

성능

이 알고리즘은 O(n) 시간 복잡도로 동작한다. 배열의 각 요소를 현재 최소값/최대값과 비교하기 때문에, 알고리즘 실행 시간은 배열 길이에 비례한다.

작성자: Chris Pilcher