[백준] 단계별로 풀어보기(단계:26, 투 포인터,JAVA)1806번, 부분합

문제 링크

1806번: 부분합

---

주의사항

• JAVA를 사용하여 프로그램을 사용하였습니다.
• 백준에서 코드를 작성하였을 때 아래 형태에서 Main에서 결과가 출력되어야 합니다.

public class Main{ 	
	public static void main(String[] args){
    }
}

---

문제 설명

---

접근 방법

투 포인터는 두 가지의 위치를 가리키는 포인터 Start, End를 이용하여 1차원 배열에 저장된 값들에 범위를 더하여 해당하는 값을 구하거나 포인터가 가리키는 값을 더해서 원하는 값을 구할 수 있도록 하는 알고리즘입니다.

 

투 포인터를 사용할 때에는 주로 정렬한 상태에서 사용합니다.

이 문제에 핵심은

1. 수열의 값에서 합이 S 이상이 되며 가장 짧은 범위의 길이를 출력해야한다.

2. S이상의 합을 만들지 못하면 0을 출력한다.

 

투 포인터 알고리즘에서는 위치를 가리키는 2가지 포인터를 설정하였습니다.

Start = 0

End = 0

 

이후 저는 특성합을 오름차순으로 정렬한 뒤에 아래에 규칙대로 탐색하였습니다.

1. start의 값 ~ end의 값 >= 0 : Start + 1, 범위 길이 측정

2. start의 값 ~ end의 값 < 0 : End + 1

 

위 규칙이 나온 이유는

start의 값 ~ end의 값이 0 이상일 때 조건에 만족함으로 해당 범위보다 작지만 조건 만족하는 길이를 찾는다.

 

범위가 줄어들어야 하기 때문에 Start + 1을 해주어야 합니다.

 

start의 값 ~ end의 값이 음수이면 범위의 값을 더 높여야 하기 때문에 End + 1을 해주어야 합니다.

 

입력 수열이 {3, 5, 1, 4, 9}, S = 10일 때 규칙을 적용하는 과정을 살펴보면

3	5	1	4	9
Start,End

Start(1) ~ End(1) = 3(3<10)

규칙2 적용 → End + 1

 

3	5	1	4	9
Start	End

Start(1) ~ End(2) = 8(8<10)

규칙 2 적용 → End + 1

 

3	5	1	4	9
Start		End

Start(1) ~ End(3) = 9(9<10)

규칙 2 적용 → End + 1

 

3	5	1	4	9
Start			End

Start(1) ~ End(4) = 13(13>=10)

길이 저장 = (4 - 1) + 1 = 4

규칙 1 적용 → Start + 1

 

3	5	1	4	9
	Start		End

Start(2) ~ End(4) = 10(10>=10)

길이 저장 = (4 - 2) + 1 = 3

규칙 1 적용 → Start + 1

 

3	5	1	4	9
		Start	End

Start(3) ~ End(4) = 5(5<10)

규칙 2 적용 → End + 1

 

3	5	1	4	9
		Start		End

Start(3) ~ End(5) = 14(14>=10)

길이 저장 = (5 - 3) + 1 = 3

규칙 1 적용 → Start + 1

 

3	5	1	4	9
			Start	End

Start(4) ~ End(5) = 13(13>=10)

길이 저장 = (5 - 4) + 1 = 2

규칙 1 적용 → Start + 1

 

3	5	1	4	9
				Start,End

Start(5) ~ End(5) = 10(9<10)

규칙 2 적용 → End + 1

 

End 수열 범위 벗어남으로써 탐색 종료!

 

s보다 큰 범위 중 가장 길이가 짧었던 2를 결과로 출력합니다.

 

 

문제를 해결한 알고리즘의 과정입니다.

1. 입력값(수열, S)를 저장합니다.

2. 위 규칙을 적용합니다.

3. 조건을 만족한 범위 중 가장 짧은 길이를 결과로 출력합니다.

4. 조건에 만족하는 범위가 없을 경우 0을 결과로 출력합니다.

 

• BufferedReader를 사용하여 입력 값을 받았습니다.
• StringTokenizer를 통해 수열의 값을 분리하였습니다.
• 규칙을 적용하여 S이상의 범위 합을 가지는 범위의 최단길이를 구하는 cal함수를 만들었습니다.
• BufferedWriter에 조건 존재하면 최단길이, 존재하지 않으면 0을 저장하였습니다.
• BufferedWriter에 저장된 결과값을 출력하였습니다.

• cal은 투 포인터 알고리즘을 통해 Start, End를 이용해서 경우의 수를 구하였습니다.
• cal은 반복문을 통해 위 규칙을 적용하였습니다.

import java.io.*;
import java.util.*;
public class Main{
	static int[] num;	//수열 값 저장 배열
    public static void main(String[] args) throws IOException{
    	BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        //입력값 처리하는 BufferedReader
    	BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        //결과값 출력하는 BufferedWriter
        //--------입력값 저장 및 배열 초기화--------
    	StringTokenizer st = new StringTokenizer(br.readLine()," ");
    	int N = Integer.parseInt(st.nextToken());
    	int S = Integer.parseInt(st.nextToken());
    	num = new int[N];
    	st = new StringTokenizer(br.readLine()," ");
    	for(int i=0;i<N;i++) 
    		num[i] = Integer.parseInt(st.nextToken());
    	int result = cal(N,S);		//함수 실행
    	if(result == Integer.MAX_VALUE)	//조건 만족하는 범위 없을 때
    		bw.write("0\n");
    	else
    		bw.write(result + "\n");	//최단 길이 BufferedWriter 저장
    	bw.flush();		//결과 출력
    	bw.close();
    	br.close();
    }
    //투 포인터를 이용한 S 이상 범위합의 최단 길이 구하는 함수
    static int cal(int N, int S) {
    	int start = 0;		//Start 포인터
    	int end = 0;		//End 포인터
    	int length = Integer.MAX_VALUE;
    	int temp = num[start];
    	while(true) {
    		if(temp<S) {	//조건 1.
    			end++;
    			if(end==N)
    				break;
    			temp += num[end];	//End값 증가시 현재 범위 값에 num[end+1]값 증가
    		}else {		조건 2.
    			length = Math.min(length, end - start + 1);
    			temp -= num[start];	//Start값 증가시 현재 범위 값에 num[start]값 감소
    			start++;
    		}
    	}
    	return length;		//결과 반환
    }
}