배열 문제에서도 연속된 구간을 다루는 경우가 자주 나옵니다.
이때 모든 구간을 직접 확인하면 코드가 금방 복잡해지고, 시간도 오래 걸릴 수 있습니다.
이번 글에서는 슬라이딩 윈도우를 이용해
서로 다른 종류가 K개 이하인 가장 긴 연속 구간의 길이를 구하는 문제를 정리해보겠습니다.
문제
동영상 앱에서 사용자가 연속해서 본 콘텐츠 장르 기록이 배열로 주어집니다.
예를 들어 다음과 같다고 해보겠습니다.
["게임", "음악", "게임", "뉴스", "뉴스", "뉴스"]
정수 k가 주어질 때,
서로 다른 장르가 최대 k개 이하로만 포함되는 가장 긴 연속 구간의 길이를 구하세요.
예시
records = ["게임", "음악", "게임", "뉴스", "뉴스", "뉴스"]
k = 2
가능한 연속 구간 중 하나는 다음과 같습니다.
["게임", "뉴스", "뉴스", "뉴스"]
이 구간에는 서로 다른 장르가 "게임", "뉴스" 총 2개만 있습니다.
길이는 4입니다.
따라서 정답은 다음과 같습니다.
4
처음 떠오르는 생각
가장 단순한 방법은 모든 연속 구간을 직접 만들어 보는 것입니다.
예를 들면 다음과 같습니다.
["게임"]
["게임", "음악"]
["게임", "음악", "게임"]
["게임", "음악", "게임", "뉴스"]
...
하지만 이 방식은 기록 길이가 길어질수록 너무 느려집니다.
그래서 이 문제는 현재 보고 있는 구간을 유지하면서 조건을 벗어나면 줄이는 방식으로 풀어야 합니다.
이때 사용하는 대표적인 방법이 슬라이딩 윈도우입니다.
핵심 아이디어
우리는 배열에서 하나의 구간을 유지합니다.
[left ... right]
right는 오른쪽으로 이동하면서 장르를 추가합니다.- 서로 다른 장르가
k개를 넘으면left를 오른쪽으로 이동합니다. - 조건을 만족하는 동안 가장 긴 길이를 기록합니다.
쉽게 말하면 창문을 오른쪽으로 밀면서 보는 방식입니다.
게임 음악 게임 뉴스 뉴스 뉴스
^
left
게임 음악 게임 뉴스 뉴스 뉴스
^
right
현재 창문 안에 들어온 장르 종류가 너무 많아지면
왼쪽을 줄여서 다시 조건을 맞춥니다.
코드
def longest_window_k_types(records, k):
if k == 0:
return 0
count = {}
left = 0
answer = 0
for right in range(len(records)):
genre = records[right]
count[genre] = count.get(genre, 0) + 1
while len(count) > k:
left_genre = records[left]
count[left_genre] -= 1
if count[left_genre] == 0:
del count[left_genre]
left += 1
answer = max(answer, right - left + 1)
return answer
코드 해설
1. 종류 개수를 저장할 딕셔너리 만들기
count = {}
현재 구간 안에 어떤 장르가 몇 번 나왔는지 저장합니다.
예를 들어 현재 구간이 다음과 같다면
["게임", "게임", "뉴스"]
딕셔너리는 이렇게 됩니다.
{
"게임": 2,
"뉴스": 1
}
2. 오른쪽 포인터 이동하기
for right in range(len(records)):
genre = records[right]
right는 배열을 왼쪽에서 오른쪽으로 하나씩 확인합니다.
새로운 장르를 현재 구간에 추가합니다.
count[genre] = count.get(genre, 0) + 1
3. 서로 다른 종류가 k개를 넘으면 왼쪽 줄이기
while len(count) > k:
len(count)는 현재 구간에 있는 서로 다른 장르 개수입니다.
예를 들어 다음과 같으면 서로 다른 장르는 3개입니다.
{
"게임": 1,
"음악": 1,
"뉴스": 1
}
그런데 k = 2라면 조건을 넘은 상태입니다.
이때 left를 오른쪽으로 이동시키면서 구간을 줄입니다.
4. 개수가 0이 되면 삭제하기
if count[left_genre] == 0:
del count[left_genre]
어떤 장르가 현재 구간에서 완전히 사라졌다면 딕셔너리에서도 제거합니다.
그래야 len(count)가 정확한 서로 다른 장르 개수를 의미하게 됩니다.
5. 가장 긴 길이 갱신하기
answer = max(answer, right - left + 1)
현재 구간의 길이는 다음과 같습니다.
right - left + 1
조건을 만족하는 구간 중 가장 긴 길이를 계속 저장합니다.
실행 예시
records = ["게임", "음악", "게임", "뉴스", "뉴스", "뉴스"]
print(longest_window_k_types(records, 2))
결과는 다음과 같습니다.
4
가장 긴 연속 구간 중 하나는 다음과 같습니다.
["게임", "뉴스", "뉴스", "뉴스"]
복잡도
배열의 각 원소는 right에 의해 한 번 들어오고,
left에 의해 최대 한 번 빠져나갑니다.
따라서 시간 복잡도는 다음과 같습니다.
O(n)
딕셔너리에는 현재 구간 안의 장르 개수를 저장합니다.
공간 복잡도는 다음과 같습니다.
O(k)
정리
이 문제의 핵심은 모든 연속 구간을 직접 만들지 않는 것입니다.
대신 현재 구간을 하나 유지하면서,
- 오른쪽 값을 추가하고
- 조건을 넘으면 왼쪽을 줄이고
- 조건을 만족할 때 길이를 갱신합니다
이 흐름으로 풀면 됩니다.
배열에서 연속된 구간의 최댓값을 구하는 문제라면
먼저 슬라이딩 윈도우를 떠올려 보는 것이 좋습니다.