이번 강좌에서는 슬라이딩 윈도우 기법을 통해 실제 코딩 테스트 문제를 해결해보겠습니다. 슬라이딩 윈도우는 배열이나 리스트 내의 연속된 요소들의 부분집합을 효율적으로 처리하는 알고리즘 기법으로, 주로 구간의 합, 최대값 및 최소값 등을 다룰 때 유용합니다.
문제: 최장 부분 문자열
주어진 문자열에서 두 개의 서로 다른 문자만을 포함하는 가장 긴 부분 문자열의 길이를 구하는 문제를 다뤄보겠습니다.
문제 설명
입력: 문자열 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
이 강좌에서 배운 슬라이딩 윈도우 기법과 함께 더 많은 알고리즘 문제를 풀어보며 실력을 쌓아보세요!