21921 블로그

1. 문제

문제는 링크에 들어가면 있다.

2. 정답 코드

문제의 내 정답 코드는 다음과 같다.

def solution(N,X,array):

    if max(array) == 0 :
        print("SAD")
        return None

    # 슬라이딩 윈도우 문제라고 한다.
    # 왼쪽부터 하나씩 진행할 것임. 단, 매번 모든 값을 더하는게 아니라
    # 값을 넣었다 뺐다 하는 느낌으로 연산을 진행하는 듯하다. 이럼 매번
    # 전체 list의 합을 할 필요가 없으니 좋은 듯.
    # 시간초과 걸리는 이유가 X = 200,000 이면 매 루프마다 엄청난 연산이 필요하구나..
    # 슬라이딩 윈도우를 쓰면 이런 문제를 해결할 수 있을 듯.

    # 시작값을 최대로 초기화
    max_val = sum(array[:X])
    max_count = 1
    temp_val = max_val
    for i in range(X,N):
        temp_val += array[i]
        temp_val -= array[i-X]

        if max_val == temp_val :
            max_count += 1
        elif max_val < temp_val :
            max_val = temp_val
            max_count = 1

    print(max_val)
    print(max_count)

    return None

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

3. 풀이 및 생각

문제 풀이

이 문제는 간단한 건줄 알았는데, 생각보다 sum()함수와 sort()함수가 시간이 오래 걸림을 파악했어야 하는 문제다. 예를들어 N= 250,000 이고 X = 10,000이라면, 모든 수를 훑어보며 매번 sum을 하는 것은 너무나도 많은 연산량이 필요하게 될 것이다.

따라서 이 문제는 재밌는 아이디어로 인해 풀게 된다. 바로 슬라이딩 윈도우이다.

전혀 생각지도 못했던 개념이지만 너무나도 쉬운 개념이다. 단순히 한칸씩 움직이면서 끝에 값을 더하고, 지나간 값은 빼주는 역할을 요구한다. 이렇게 되면 매 루프마다 sum()함수를 사용하지 않고 전체 합을 구할 수 있다는 장점이 있다. 그리고 심지어 dictionary를 활용하지 않아도 되서 메모리도 아낄 수 있고 말이다.

나의 생각

슬라이딩 윈도우란 개념이 처음이지만, 되게 효율을 따지는 아이디어인 것 같다. 전혀 생각지도 못함!! 이번 기회에 잘 파악하고 갈 수 있도록 하자.