[Python][백준] 21921. 블로그

링크🔗

https://www.acmicpc.net/problem/21921

---

🗒️파이썬 코드 풀이

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

sum_lst = [sum(lst[0:X])]

for i in range(0,N-X):
    tmp_sum = sum_lst[i] + lst[i+X] - lst[i] 
    sum_lst.append(tmp_sum)

if sum(lst) > 0 :
    print(max(sum_lst))
    print(sum_lst.count(max(sum_lst)))    
else : 
    print("SAD")

 

1. 입력 받은 리스트 0~X-1 까지의 합을 sum_lst 첫 번째에 넣어준다.

 

2. X일 동안 연속적으로 방문자 수를 체크하는 것이므로 슬라이딩 윈도우 방식으로 한다.

sum_lst[i]  (이전 방문자수 기록 합) +  lst[i+X] (다음날 방문자수 기록) - lst[i] (i 번째 방문자 수) 를 해주면 된다.

 

(이런 느낌으로 보면 된다.)

 

3. SAD인 경우는 리스트의 모든 값이 0인 경우이니,  모든 값들을 합해도 0이다. 

이것을 if로 필터링해서 출력 할 것들은 나눠준다

 

 

📕 내 풀이 (시간 초과)

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

sum_lst = []
for i in range(N-X+1):
    tmp_sum = sum(lst[i:i+X])
    sum_lst.append(tmp_sum)

if sum(lst) > 0 :
    print(max(sum_lst))
    print(sum_lst.count(max(sum_lst)))    
else : 
    print("SAD")

 

1.  슬라이딩 윈도우 방식으로 풀어야지, 시간 초과가 나지 않는다. 

•  1≤𝑋≤𝑁≤250,000   (X와 N의 범위보면 무분별한 반복문을 조심해야겠다는 생각이 든다.)

2. 반복문마다 매번 sum(lst[i:i+X]) 과정을 거치는데, 여기서 시간 초과가 발생한다.

 

 

📌  문제 코멘트

구현 자체도 쉽기 때문에 문제가 어렵지는 않는데,  

슬라이딩 윈도우 방식을 모르면 좀 당황 할 것 같다.

항상 시간 복작도를 계산하고, 어떤 알고리즘으로 접근할지를 생각하자 ...!!!

 

---

📚문제

찬솔이는 블로그를 시작한 지 벌써 N일이 지났다.

요즘 바빠서 관리를 못 했다가 방문 기록을 봤더니 벌써 누적 방문 수가 6만을 넘었다.

 

찬솔이는 X일 동안 가장 많이 들어온 방문자 수와 그 기간들을 알고 싶다.

찬솔이를 대신해서 X일 동안 가장 많이 들어온 방문자 수와 기간이 몇 개 있는지 구해주자.

입력

첫째 줄에 블로그를 시작하고 지난 일수 N와 X가 공백으로 구분되어 주어진다.

둘째 줄에는 블로그 시작 1일차부터 N일차까지 하루 방문자 수가 공백으로 구분되어 주어진다.

출력

첫째 줄에 X일 동안 가장 많이 들어온 방문자 수를 출력한다. 만약 최대 방문자 수가 0명이라면 SAD를 출력한다.

만약 최대 방문자 수가 0명이 아닌 경우 둘째 줄에 기간이 몇 개 있는지 출력한다.

제한

•  1≤𝑋≤𝑁≤250,000
•  0≤ 방문자 수 ≤8,000

예제 입력 1 복사

5 2
1 4 2 5 1

예제 출력 1 복사

7
1

예제 입력 2 복사

7 5
1 1 1 1 1 5 1

예제 출력 2 복사

9
2

예제 입력 3 복사

5 3
0 0 0 0 0

예제 출력 3 복사

SAD