[BOJ] Python 백준 1806번 부분합 골드 4

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

1806번: 부분합

문제 풀이

---

자연수로 이루어진 수열이므로 연속된 합을 구하는 다양한 알고리즘 중에 투 포인터(Two Pointer) 알고리즘을 사용하는 문제다.

 

만약 투 포인터에 대해 잘 모르겠다면 밑에 있는 더보기를 눌러서 설명을 보고 이해하기 바란다.

 

 

 

투 포인터 알고리즘이란 두 개의 지점을 이동시키면서 연속된 숫자의 합(구간 합)을 구하는 알고리즘이다.

 

비슷한 알고리즘으로 슬라이딩 윈도우(Sliding Window)가 있는데 이 둘의 차이점은 구간의 길이다.

 

슬라이딩 윈도우는 구간의 길이가 정해져 있고, 투 포인터는 상황에 따라 변한다.

 

또한 투 포인터는 음수가 존재할 경우 구간의 길이가 증가했을 때 구간 합이 증가할지 감소할지 보장할 수 없으므로 양의 정수만 존재할 때 사용 가능하다는 특징이 있다. 

 

그림을 통해 이해하면 쉬울 것이다.

 

 

다음과 같이 자연수로 이루어진 리스트가 있을 때 합이 5인 구간의 최소 길이를 찾는 예시를 보자.

 

이때 두 가지 변수를 Left, Right로 선언하고 처음부터 Right 변수를 오른쪽으로 움직이며 구간 합에 원소를 합하고 Left 변수를 오른쪽으로 움직이며 구간합에 원소를 빼는 방식이다.

 

 

먼저 Right 변수가 첫 번째 원소를 가리킬 때다.

 

Sum에 해당하는 원소를 더하고 5와 비교했을 때 더 작으므로 구간을 늘려야 한다.

 

따라서 Right 변수를 옮겨야 한다.

 

 

Right 변수를 옮기고 나서 구간합이 5가 되므로 이 구간의 길이를 갱신시키면 된다.

 

최소 길이를 구해야 하므로 Left 변수를 옮기면 된다.

 

 

Left 변수를 옮기고 나서 Sum이 5보다 작으므로 Right 변수를 옮긴다.

 

 

Right 변수를 옮긴 뒤 Sum이 5보다 크므로 Left 변수를 옮겨 구간 합을 더 작게 만든다.

 

 

Left 변수를 옮기고 Sum이 5보다 더 크지만 동일한 원소(구간의 길이가 1)를 가리키므로 Right 변수를 옮긴다.

 

 

Right 변수를 옮긴 뒤 Sum이 5보다 크므로 Left 변수를 옮긴다.

 

 

Left 변수를 옮긴 뒤 해당 원소를 빼주니 Sum이 5이다.

 

해당 구간의 길이는 1이므로 구간 길이를 갱신해주고 Right 변수를 옮긴다.

 

 

Right 변수를 옮기니 리스트를 벗어나므로 탐색을 종료한다.

 

인덱싱을 어떻게 구현하는지는 본인의 자유이며 인덱싱 과정이 헷갈릴 수 있기에 여러 가지 방법 중에 가장 자신한테 적합한 방식을 적용하는 편이 좋을 것 같다.

 

 

다음은 문제를 푼 전체 코드이다.

 

n,s=map(int,input().split())
left=-1
right=0
min_len=100001
num_array=list(map(int,input().split()))
temp_sum=num_array[0]
while right<n:
    if temp_sum>=s:
        if min_len>right-left:
            min_len=right-left
        left+=1
        temp_sum-=num_array[left]
    else:
        right+=1
        if right<n:
            temp_sum+=num_array[right]
if min_len==100001:
    print(0)
else:
    print(min_len)

 

문제에서 수열의 길이 N은 100000 미만이므로 100000 이상의 숫자 중 아무거나 구간의 최소 길이로 정하고 그걸 갱신하면 최소 길이를 구할 수 있다.

 

만약 처음에 정한 숫자가 그대로 있다면 합이 s보다 큰 구간이 없단 뜻이며 4번째 줄에선 선언하고, 17번째 줄에선 판단하도록 구현했다.

 

7번째 줄의 while문에서는 right 변수가 수열의 길이를 넘어가면 안 되므로 길이(n) 미만일 때까지만 반복을 한다.

 

또한 while문 내부에서는 구간합이 S이상이면 길이를 갱신하고 Left를 이동시켜 원소를 구간합에서 빼고 구간합이 S미만이면 Right를 이동시켜 원소를 구간합에 더하도록 구현했다.

 

결과 화면

 

인덱싱 과정이 다소 헷갈릴 수 있는 알고리즘이라서 소수의 원소를 집어넣고 접근하는 과정을 하나씩 출력하다 보면 실수를 줄일 수 있을 것이다.