Baekjoon Online Judge

algorithm practice

- 단계별 문제풀기

26. 투 포인터

투 포인터 알고리즘과 meet in the middle 알고리즘을 배워 봅시다.

Java / Python

3. 부분합

1806번

한 쪽에서 두 포인터를 이동시키는 문제

이번 문제는 10,000 이하의 자연수로 이루어진 길이 N짜리 수열이 주어질 때, 이 수열에서 연속된 수들의 부분합 중에 그 합이 S 이상이 되는 것 중, 가장 짧은 것의 길이를 구하는 프로그램을 작성하는 문제입니다.

부분합이란 시작점과 끝점을 정해서 해당 구간 내의 원소들의 합을 구하는 것입니다.
이 문제는 굳이 부분합을 사용하지 않고, 투 포인터로도 가능한 문제입니다.
파이썬은 두 가지 방식 모두로 풀었습니다.

• Java

import java.io.*;
import java.util.*;

public class Main {  
    
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));   
		StringTokenizer st = new StringTokenizer(br.readLine()); 
        
		int N = Integer.parseInt(st.nextToken()); 
		long S = Long.parseLong(st.nextToken());
        
		int[] arr = new int[N]; 
        
		st = new StringTokenizer(br.readLine()); 
		for(int i = 0; i < N; i++){
			arr[i] = Integer.parseInt(st.nextToken());
		}
        
		int result = 100001, sum = 0;
		int point1 = 0, point2 = 0;
		while(true){
			if(sum >= S){
				sum -= arr[point1++];
				result = Math.min(result, (point2 - point1) + 1);
			}
			else if(point2 == N) break;
			else sum += arr[point2++];
		}
        
		if(result == 100001) bw.write("0\n");
		else bw.write(result + "\n");
        
		bw.flush();
		br.close();
		bw.close();
	}
}

• Python

투 포인터 방식

import sys

N, S = map(int, sys.stdin.readline().split())
arr = list(map(int, sys.stdin.readline().split()))

start, end, temp = 0, 0, 0
result = 100001

while True:
    if temp >= S: 
        result = min(result, end - start)
        temp -= arr[start]
        start += 1
    elif end == N:
        break
    else:
        temp += arr[end]
        end += 1
        
if result == 100001:
    result = 0
        
print(result)

부분합 방식

import sys

N, S = map(int, sys.stdin.readline().split())
arr = list(map(int, sys.stdin.readline().split()))

prefix = [0]*(N+1)
start, end = 0, 1

for i in range(1, N+1):
    prefix[i] = prefix[i-1] + arr[i-1]

result = 100001
    
while start < N:
    if prefix[end] - prefix[start] >= S: 
        result = min(result, end - start)
        start += 1
    else:
        if end < N:
            end += 1
        else: 
            start += 1
        
if result == 100001:
    result = 0
        
print(result)