[백준][파이썬]21921.블로그 -슬라이딩윈도우

아래의 문제는 '백준'의 알고리즘 문제 내용이며 코드는 직접 푼 내용입니다.

---

 

21921. 블로그

문제 및 입출력 

입출력예시 

---

나의시도

앞에 부분합(구간합)알고리즘처럼 연속적인 x일동안 방문자수들의 합을 계산해두려고 했다.

연속적인 x일동안 방문자수는 i부터 i+x만큼 split하고 sum하면 되지 않을까 했다...

대신 그 i는 끝까지 안돌고 x뺀만큼 하고 인덱스니까 +1해서 거기까지..?

import sys
input=sys.stdin.readline

N,X=map(int,input().split())
data=list(map(int,input().split()))

#구간합 알고리즘 변형
prefix_sum=[] #접두사합 배열

#접두사합 배열 계산 (X단위로 부분합저장)
for i in range(len(data)-X+1):
    sum_value=0
    print(data[i:i+X])
    sum_value=sum(data[i:i+X]) #부분합
    prefix_sum.append(sum_value) #부분합결과 미리 저장해둠

#print(prefix_sum)
max_ans=max(prefix_sum)
if max_ans == 0:
    print("SAD")
else:
    print(max_ans)
    print(prefix_sum.count(max_ans))

하지만 시간초과가 났다..

흠 이렇게 계산하고 난 다음에 원하는 정답을 뽑아서 그런가..그리고 for 하나로 다 부분합계산하는 것도 좀 그럴듯..

하긴 계산하면서 바로 정답을 뽑아내는게 더 효율적일 순 있겠다.

---

풀이과정

그래서 약간의 구글링을 통해 슬라이딩 윈도우 방법으로 한 코드를 이해해봤다

import sys
input=sys.stdin.readline

N,X=map(int,input().split())
data=list(map(int,input().split()))

if max(data) == 0:
    print("SAD")
else:
	#value초기화
    value = sum(data[:X]) #X개씩 나눠서 sum
    
    max_value=value
    max_cnt=1

    for i in range(X,N):
    	#슬라이딩 윈도우진행
        value+=data[i] #슬라이딩윈도우 앞에
        #print("+",data[i])
        value-=data[i-X] #슬라이딩윈도우 뒤에값
        #print("-",data[i-X])

		#value의 최대값 찾음
        if value > max_value:
            max_value=value
            max_cnt=1
            
        #최대값 count    
        elif value == max_value:
            max_cnt+=1
    print(max_value)
    print(max_cnt)

 

• 일단, 나는 마지막에 출력결과에 대한 걸 작성했는데 정답코드에선 else에서 바로 정답을 뽑을수 있다.
• 그리고 초기화 sum값을 처음 x까지 split한 sum값으로 지정한다.
• 구간x부터 배열의 끝까지 이제 슬라이딩윈도우를 진행해서 value를 구한다.
  • 슬라이딩윈도우가 오른쪽으로 이동한만큼 value를 더하고
  • 슬라이딩윈도의 바로앞에 값? 슬라이딩윈도우 크기-1 만큼 겹치는 값?을 value를 뺀다
• 그렇게 구한 value의 max값을 찾고, 또한 그 max값이 몇번 나온지도 count하면 된다.

어떻게 슬라이딩윈도우가 동작되는지 디버깅결과를 보면 쉽게알수 있다

---

슬라이딩 윈도우

슬라이딩 윈도우는 크기가 고정적인 창문(특정 범위)을 옆으로 밀면서(->) 이동하는 방식이다. 

그리고 매 순간 창문을 통해 보이는 세상속에서 정보(예를 들면 합)를 유출한다.

Window를 한 칸 옮기면 (W-1) 칸은 겹친다 ! 즉, 중복된 항목이 W-1 이므로 이전의 결과를 최대한 응용!

---

배운점

• 슬라이딩윈도우
• 계산하고 정답을 다시 찾으려고 탐색하지 말고 바로 답을 찾을 수 있도록

---

참고한 블로그

https://welog.tistory.com/317

welog