boj 1806

처음에는 해당 문제를 보고 슬라이딩 윈도우를 활용하여 슬라이딩 윈도우 크기를 점차 늘려가며 해결하려 했었다.

int sum = 0;
for(int i =1; i<=10; i++){ // 윈도우 크기 1부터 10까지 
	
	for(int j=0; j<i; j++){
    	sum = arr[i];
    }  // 슬라이딩 윈도우 처음 합 크기 
    
    boolean check = false;
    for(int i=1; i<=n-i; i++){
    	sum = sum - arr[i-1] + arr[i+x-1];
        if(sum >= m){
    	check = true;
    	break;
    }
    if(check){
    	break;
    }
   }
    
    
}

허나 해당 코드는 최악의 경우 o(n^2) 이라는 시간이 필요하고
당연히 해당 풀이는 시간초가라는 불상사가 나 버렸다....

그럼 o(n) 방식이 어떻게 일어진다는 것인가

바로

투포인터

투포인터 방식이다

투포인터 방식을 간단하게 설명하자면

이런식으로 좌표를 넣고 start 와 end를 움직여 가면서 조절을 하는게 투포인터 방식이다

문제풀이

그럼 이번문제를 투포인터로 어떻게 해결할 수 있을 까?

1. start end 까지의 합이 m 보다 작으면 end 를 1더해준다 sum에 end 더해준다
2. 크거나 같을 때 start end를 이용하여 길이를 구해 min을 구한다
3. 크거나 같으면 start를 1더해준다 sum에 start 빼준다
4. start > end 보다 커지면 멈춘다
5. end가 끝까지오면 sum 이 m 보다 작으면 멈춘다

그럼 풀이로 풀어보도록 하겠다

int start = 0;
int end = 0; // start end 좌표 지정
int sum = arr[0];

while(start<= end){ 4.
	//1. 
    if(sum <m){
    	end = end +1;
        sum = sum +arr[end];
    }
    //2.3
    if(sum >=m){
		2.	   
    	int length = start+end -1;
        if(length < min){
        	length = min;
        }
        3.
        start = start+1;
        sum = sum -arr[start];
    }
  // 5.
  if(end == n-1){
  	if(sum < m){
    	break;
    }
  }
}

전체 코드

 private static int[] arr;
    public static void main(String[] args) throws IOException{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        StringTokenizer st;
        st = new StringTokenizer(br.readLine());

        int n = Integer.parseInt(st.nextToken());
        int s = Integer.parseInt(st.nextToken());

        arr = new int[n];
        st = new StringTokenizer(br.readLine());
        for(int i=0; i<arr.length; i++){
            arr[i] = Integer.parseInt(st.nextToken());
        }


        int start = 0;
        int end = 0;
        int sum  = arr[0];
        int min = Integer.MAX_VALUE;


        while(start<=end){

            if(sum<s){
                // end 이동
                end = end+1;
                sum += arr[end];
            }else if(sum >= s){
                //start 이동
                int length = end - start + 1;
                if (min > length) {
                    min = length;
                }
                sum -= arr[start];
                start = start +1;
            }
            if(end ==n-1){
                if(sum < s){
                    break;
                }

            }
        }

        if(min != Integer.MAX_VALUE){
            System.out.println(min);
        }else{
            System.out.println(0);
        }




    }

---

만약 고정된 크기에서 구한다 -> 슬라이딩 윈도우
현재 처럼 가변된 크기에서 구한다 -> 투포인터