스위프트 코딩테스트 강좌, 슬라이딩 윈도우

이번 강좌에서는 슬라이딩 윈도우 기법을 통해 실제 코딩 테스트 문제를 해결해보겠습니다. 슬라이딩 윈도우는 배열이나 리스트 내의 연속된 요소들의 부분집합을 효율적으로 처리하는 알고리즘 기법으로, 주로 구간의 합, 최대값 및 최소값 등을 다룰 때 유용합니다.

문제: 최장 부분 문자열

주어진 문자열에서 두 개의 서로 다른 문자만을 포함하는 가장 긴 부분 문자열의 길이를 구하는 문제를 다뤄보겠습니다.

문제 설명

입력: 문자열 s
출력: 두 개의 서로 다른 문자를 포함하는 가장 긴 부분 문자열의 길이

예제

입력: "abcabcbb"
출력: 3
설명: 가장 긴 부분 문자열은 "abc"이고, 두 개의 서로 다른 문자를 포함하지 않으므로 "bca" 또는 "cab"가 가장 긴 부분 문자열입니다.

문제 접근법

이 문제를 해결하기 위해 슬라이딩 윈도우 기법을 사용할 것입니다. 슬라이딩 윈도우는 두 개의 포인터를 사용하여 특정 조건을 만족하는 구간을 동적으로 조정해 나가는 기법입니다.

단계별 접근 과정

1단계: 함수 초기화

우선, 문자열의 길이와 결과를 저장할 변수를 초기화합니다. 슬라이딩 윈도우의 시작과 끝을 나타낼 포인터를 설정합니다.

let s = "abcabcbb"
var left = 0
var right = 0
var maxLength = 0
var charFrequency = [Character: Int]()

2단계: 윈도우 확장

오른쪽 포인터를 한 칸씩 이동시키며 현재 문자에 대해 빈도를 기록합니다. 그렇게 해주면 현재 윈도우에 포함된 문자의 빈도수를 알 수 있습니다.

while right < s.count {
    let currentChar = s[right]
    charFrequency[currentChar, default: 0] += 1
    right += 1

3단계: 조건 검사 및 윈도우 축소

문자열의 문자 수가 두 개를 초과하면 왼쪽 포인터를 이동시켜서 문자의 수를 조정합니다. 이 과정을 반복하여 특정 조건을 만족하는 경우 윈도우의 크기를 계산하여 최대 길이를 업데이트 합니다.

while charFrequency.count > 2 {
    let leftChar = s[left]
    charFrequency[leftChar]! -= 1
    if charFrequency[leftChar] == 0 {
        charFrequency.removeValue(forKey: leftChar)
    }
    left += 1
}
maxLength = max(maxLength, right - left)

4단계: 함수 완성

이 모든 과정을 통해 완성된 코드는 다음과 같습니다:

func lengthOfLongestSubstringTwoDistinct(_ s: String) -> Int {
    var left = 0, right = 0, maxLength = 0
    var charFrequency = [Character: Int]()

    let charArray = Array(s)

    while right < charArray.count {
        let currentChar = charArray[right]
        charFrequency[currentChar, default: 0] += 1
        right += 1

        while charFrequency.count > 2 {
            let leftChar = charArray[left]
            charFrequency[leftChar]! -= 1
            if charFrequency[leftChar] == 0 {
                charFrequency.removeValue(forKey: leftChar)
            }
            left += 1
        }
        maxLength = max(maxLength, right - left)
    }
    return maxLength
}

5단계: 시간 복잡도 분석

이 알고리즘의 시간 복잡도는 O(n)입니다. 각각의 문자를 한 번씩 방문하기 때문에 효율적입니다. 공간 복잡도는 O(1)로, 최대 문자 집합이 고정되어 있기 때문입니다.

결론

슬라이딩 윈도우 기법은 특정 조건을 만족하는 연속된 부분을 탐색할 때 매우 유용합니다. 이 방법을 통해 많은 알고리즘 문제를 효율적으로 해결할 수 있습니다. 아래 코드를 스위프트로 직접 실행해보세요!

let testString = "abcabcbb"
let result = lengthOfLongestSubstringTwoDistinct(testString)
print(result)  // 출력: 3

이 강좌에서 배운 슬라이딩 윈도우 기법과 함께 더 많은 알고리즘 문제를 풀어보며 실력을 쌓아보세요!