3Sum과 4Sum

3Sum과 4Sum은 널리 알려진 알고리즘 문제인 2Sum의 확장 버전이다.

3Sum 문제 해결

정수 배열이 주어졌을 때, 배열에서 3개의 값을 선택해 그 합이 목표 숫자가 되는 모든 부분집합을 찾는 문제다.

주의: 해결책으로 제시된 부분집합은 중복된 세 쌍을 포함해서는 안 된다.

예를 들어, 배열이 [-1, 0, 1, 2, -1, -4]이고 목표 숫자가 0인 경우:
해결책 집합은 [[-1, 0, 1], [-1, -1, 2]]가 된다. // 배열에 있는 두 개의 -1 값은 서로 다른 값으로 간주된다.

이 알고리즘을 해결하는 데는 두 가지 주요 절차가 있다. 배열을 정렬하는 것과 중복을 피하는 것이다.

정렬

입력 배열을 정렬하면 두 가지 강력한 가정을 할 수 있다:

이 두 가지 규칙을 활용해 효율적인 알고리즘을 만들 수 있다.

중복 제거하기

배열을 미리 정렬하면 중복된 값들이 서로 인접하게 배치된다. 따라서 인접한 값을 비교하면서 중복을 건너뛰면 된다:

extension Collection where Element: Equatable {
  
  /// 정렬된 컬렉션에서 주어진 인덱스를 고유한 요소를 가리키는 다음 인덱스로 대체한다.
  ///
  /// - Parameter index: 컬렉션의 유효한 인덱스. `index`는 `endIndex`보다 작아야 한다.
  func formUniqueIndex(after index: inout Index) {
    var prev = index
    repeat {
      prev = index
      formIndex(after: &index)
    } while index < endIndex && self[prev] == self[index]
  }
}

비슷한 방식으로 주어진 인덱스의 이전 고유 인덱스를 얻는 구현도 가능하다:

extension BidirectionalCollection where Element: Equatable {
  
  /// 정렬된 컬렉션에서 주어진 인덱스를 고유한 요소를 가리키는 이전 인덱스로 대체한다.
  ///
  /// - Parameter index: 컬렉션의 유효한 인덱스. `index`는 `startIndex`보다 커야 한다.
  func formUniqueIndex(before index: inout Index) {
    var prev = index
    repeat {
      prev = index
      formIndex(before: &index)
    } while index > startIndex && self[prev] == self[index]
  }
}

부분 집합 조합하기

세 숫자를 나타내기 위해 세 개의 인덱스를 추적한다. 현재 시점의 합은 array[l] + array[m] + array[r]이다:

      m ->      <- r
[-4, -1, -1, 0, 1, 2]
  l

이 접근법은 2Sum 알고리즘을 알고 있다면 매우 직관적이다. l을 배열 전체를 순회하며 반복한다. 각 반복마다 l 이후의 요소에 대해 2Sum 알고리즘을 적용한다. 인덱스를 이동할 때마다 합을 확인하여 일치하는 조합을 찾는다. 다음은 해당 알고리즘이다:

func threeSum<T: BidirectionalCollection>(_ collection: T, target: T.Element) -> [[T.Element]] where T.Element: Numeric & Comparable {
  let sorted = collection.sorted()
  var ret: [[T.Element]] = []
  var l = sorted.startIndex
  
  ThreeSum: while l < sorted.endIndex { defer { sorted.formUniqueIndex(after: &l) }
    var m = sorted.index(after: l)
    var r = sorted.index(before: sorted.endIndex)
    
    TwoSum: while m < r && r < sorted.endIndex { 
      let sum = sorted[l] + sorted[m] + sorted[r]
      if sum == target {
        ret.append([sorted[l], sorted[m], sorted[r]])
        sorted.formUniqueIndex(after: &m)
        sorted.formUniqueIndex(before: &r)
      } else if sum < target {
        sorted.formUniqueIndex(after: &m)
      } else {
        sorted.formUniqueIndex(before: &r)
      }
    }
  }
  
  return ret
}

4Sum 문제

정수 배열 S가 주어졌을 때, 배열에서 4개의 값을 선택해 그 합이 목표값(target)과 일치하는 모든 부분집합을 찾는 문제이다.

주의: 해결책 집합에는 중복된 4개의 값 조합(quadruplets)이 포함되어서는 안 된다.

이 문제는 주어진 배열에서 4개의 숫자를 선택해 그 합이 특정 값과 일치하는 모든 조합을 찾는 것이다. 단, 동일한 조합이 여러 번 포함되지 않도록 주의해야 한다. 예를 들어, 배열이 [1, 0, -1, 0, -2, 2]이고 목표값이 0인 경우, 가능한 조합은 다음과 같다:

이 문제를 해결하려면 배열을 정렬한 후, 두 개의 포인터를 사용해 가능한 조합을 탐색하는 방법을 고려할 수 있다. 이때 중복된 조합이 발생하지 않도록 주의해야 한다.

해결 방법

Foursum은 threeSum 알고리즘을 자연스럽게 확장한 것이다. threeSum에서는 세 개의 인덱스를 추적했다:

      m ->      <- r
[-4, -1, -1, 0, 1, 2]
  l

fourSum에서는 네 개의 인덱스를 추적한다:

         mr ->  <- r
[-4, -1, -1, 0, 1, 2]
  l  ml ->

아래는 fourSum을 구현한 코드다. threeSum과 매우 유사하다는 점을 확인할 수 있다:

func fourSum<T: BidirectionalCollection>(_ collection: T, target: T.Element) -> [[T.Element]] where T.Element: Numeric & Comparable {
  let sorted = collection.sorted()
  var ret: [[T.Element]] = []
  
  var l = sorted.startIndex
  FourSum: while l < sorted.endIndex { defer { sorted.formUniqueIndex(after: &l) }
    var ml = sorted.index(after: l)
    
    ThreeSum: while ml < sorted.endIndex { defer { sorted.formUniqueIndex(after: &ml) }
      var mr = sorted.index(after: ml)
      var r = sorted.index(before: sorted.endIndex)
      
      TwoSum: while mr < r && r < sorted.endIndex {
        let sum = sorted[l] + sorted[ml] + sorted[mr] + sorted[r]
        if sum == target {
          ret.append([sorted[l], sorted[ml], sorted[mr], sorted[r]])
          sorted.formUniqueIndex(after: &mr)
          sorted.formUniqueIndex(before: &r)
        } else if sum < target {
          sorted.formUniqueIndex(after: &mr)
        } else {
          sorted.formUniqueIndex(before: &r)
        }
      }
    }
  }
  return ret
}

Swift Algorithm Club의 Kai Chen과 Kelvin Lau가 작성함