one Book a Day

슬라이딩 윈도우 import sys input = sys.stdin.readline N, B, W = map(int, input().split()) stone = input().rstrip() # 까만색 B개 이하, 흰색은W개 이상 left = 0 w_cnt = 0 b_cnt = 0 max_len = 0 for right in range(N): if stone[right]=='W': w_cnt += 1 else: b_cnt += 1 while b_cnt > B: if stone[left]=='W': w_cnt -= 1 else: b_cnt -= 1 left += 1 if w_cnt>=W: max_len = max(max_len,right-left+1) print(max_len)

간격 컨트롤이 아닌 내부 요소들의 합으로 컨트롤하는 슬라이딩 윈도우. import sys input = sys.stdin.readline N = int(input()) prex_sum, left = 0, 0 answer = 0 # 슬라이딩 윈도우 for right in range(1,N+1): # 결론적으로 end는 기존 슬라이딩 윈도우 처럼 일정 간격이 고정이 아니라 # 일정 합 이상이되면 알아서 그 간격이 줄어드는 시스템이므로 한번 순회로 전부 조사 가능. while left < N and prex_sum < N: prex_sum += left+1 left += 1 if prex_sum == N: answer += 1 prex_sum -= right print(answer)

원형 큐이므로 배열 두개 이어주고 순회. for 문을 돌려 right는 따로 컨트롤x 길이가 k가 되면 최댓값 갱신, left삭제, left idx 증가를 반복.ㄴ import sys input = sys.stdin.readline from collections import defaultdict N, d, k, c = map(int,input().split()) sushi = [] for _ in range(N): sushi.append(int(input())) sushi.extend(sushi) left = 0 right = 0 max_cnt = 0 eat = defaultdict(int) eat[c] += 1 for right in range(len(sushi)): eat[sushi[right]] +..

투포인터는 연속 구간의 길이가 가변적으로 변할 때 O(2*N)으로 풀도록 도와줌. 슬라이딩 윈도우는 구간의 크기가 고정일때. 둘다 start, end 포인트 사용(슬라이딩 윈도우는 end가 그냥 배열 포인터긴 함.) 하지만 둘다 연속적인 값들을 이용해 풀어나가는 한계가 있음. 기존 배열의 구간합 구하는 코드 배열 크기에서 구간의 길이k만큼의 모든 배열의 합을 순회하며 계산. import sys def max_sub_array(arr, k): maxsum = -sys.maxsize - 1 arraysize = len(arr) for i in range(arraysize - k + 1): current_sum = 0 for j in range(i, i + k): current_sum += arr[j] max..