21921. 블로그
접근 방식
너무 재밌는 문제였다!!
슬라이딩 윈도우가 뭐야 했는데 그걸 알게 해 준 문제!! 평생 모를 뻔 했어요...
우선 시간초과가 났던 내 코드다.
import sys
input = sys.stdin.readline
N, X = map(int, input().rstrip().split())
visitors = list(map(int, input().rstrip().split()))
if max(visitors) == 0: # 최대 방문자가 0인 경우
print("SAD")
else:
max_visitor = 0 # 최대 방문자수
duration = 1 # 기간
for i in range(N):
tmp = sum(visitors[i:i+X])
if tmp == max_visitor: # 최대 방문자수가 나오는 기간이 반복되는 경우
duration += 1
else:
max_visitor = max(max_visitor, tmp)
print(max_visitor, duration, sep='\n')처음 접근은 N번의 반복문 내부에서 X일동안의 합계를 구한 뒤,
기존 최댓값과 비교 후 같으면 지속 일수의 갱신을, 더 크다면 최댓값의 갱신을 해주도록 코드를 구현했다.
뭐야 너무 쉽잖아!했는데 시간초과가 나서 다시 코드를 보니,
반복문의 구간이 되는 X, N의 범위가 1 <= X <= N <= 250,000이었다 쩝...
아무리 생각해도 반복문을 최소화할 수 있는 방법이 떠오르지 않아서
풀이를 참고한 결과 '슬라이딩 윈도우'를 사용해 풀이하는 문제였다.
슬라이딩 윈도우
슬라이딩 윈도우 알고리즘은 ~크기가 고정적인 창문(특정한 범위)를 옆으로 밀어가며 이동하는 알고리즘~이다.
윈도우를 한 칸 옮길 경우 W-1칸이 겹치게 되므로,
중복되는 범위에 대한 이전 결과를 최대한으로 응용해 효율을 높일 수 있는 방법이다.
문제에 적용한 코드를 통해 슬라이딩 윈도우 알고리즘에 대해 조금 더 이해해보자.
max_visitor = sum(visitors[0:X]) # 왼쪽부터 시작(슬라이딩 윈도우)
value = max_visitor
duration = 1
for i in range(X, N):
value -= visitors[i-X] # 왼쪽 한 칸 빼고
value += visitors[i] # 오른쪽 한 칸 더하고
if value > max_visitor: # 최댓값 갱신하고
max_visitor = value
duration = 1
elif value == max_visitor: # 같은 값 또 나오면 반복횟수 갱신하고
duration += 1초기 max_visitor를 셋팅해주는 과정에서 합계를 구할 범위를 0 ~ X으로 가장 왼쪽부터 시작해줬다.
반복문의 실행 범위는 X ~ N-1으로 이전에 내가 작성했던 코드에서의 0 ~ N-1보다 시간복잡도 측면에서 효율적이다.
X부터 N까지 반복하며 한 칸씩 오른쪽으로 이동할 것이기에
1. value -= visitors[i-X] 왼쪽 한 칸 빼고
2. value += visitors[i] 오른쪽 한 칸 더하고
위 두 과정을 반복하며 인덱스를 순회한다.
슬라이딩 윈도우 알고리즘을 사용하면 연산 시간 단축에 큰 이점이 생긴다고 한다!
잘 기억해둬야지 🧠⚡️
투포인터
슬라이딩 윈도우 알고리즘에 대해 자료를 찾아보면서 투포인터 알고리즘도 정말 많이 언급되는 것을 발견했다.
슬라이딩 윈도우 vs 투포인터 - 공통점
슬라이딩 윈도우 알고리즘과 투포인터 알고리즘 모두
선형 공간(1차원 배열)을 2회 이상 반복해 탐색해야 하는 경우에
O(N^2) 이상 소요되는 시간 복잡도를 부분 배열의 활용으로 O(N)까지 줄일 수 있다.
슬라이딩 윈도우 vs 투포인터 - 차이점
1️⃣ 부분 배열 길이의 변화 여부
- 투포인터 알고리즘 : 부분 배열의 길이 - 가변적
- 슬라이딩 윈도우 알고리즘 : 부분 배열의 길이 - 고정적
2️⃣ 부분 배열 구간을 정하는 포인터
- 투포인터 알고리즘 : 부분 배열의 길이가 가변적이므로 구간을 정할 2개의 포인터 변수 필요
- 슬라이딩 윈도우 알고리즘 : 부분 배열의 길이가 고정적이므로 포인터 변수가 2개일 필요 X
- 고정적인 부분 배열 크기를 나타내는 변수가 있다면?
- 포인터 변수가 하나만 있어도 부분배열의 크기를 알고 있기에 끝이 어딘지 알 수 있음
- 고정적인 부분 배열 크기를 나타내는 변수가 있다면?
투포인터 알고리즘과 관련해서는 잘 정리해주신 글이 있어 링크를 남긴다!
다음에 투포인터 알고리즘을 중점적으로 다루는 문제에서 다시 제대로 정리하려 한다.
최종 코드
import sys
input = sys.stdin.readline
N, X = map(int, input().rstrip().split())
visitors = list(map(int, input().rstrip().split()))
if max(visitors) == 0: # 최대 방문자가 0인 경우
print("SAD")
else:
max_visitor = sum(visitors[0:X]) # 왼쪽부터 시작(슬라이딩 윈도우)
value = max_visitor
duration = 1
for i in range(X, N):
value -= visitors[i-X] # 왼쪽 한 칸 빼고
value += visitors[i] # 오른쪽 한 칸 더하고
if value > max_visitor: # 최댓값 갱신하고
max_visitor = value
duration = 1
elif value == max_visitor: # 같은 값 또 나오면 반복횟수 갱신하고
duration += 1
print(max_visitor, duration, sep='\n')배운점
▶️ 문제를 풀 때 제대로 돌아가도 시간 초과가 나는 경우가 많다. 시간복잡도를 고려해서 코드 짜는 습관 기르기!
▶️ 슬라이딩 알고리즘은 선형 자료구조에서 왼쪽부터 시작 ➡️ 한 칸씩 오른쪽으로 이동
