투포인터 관련 문제 모음

문제 1

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

시작 포인트와 엔드 포인트 지정, while문을 통해 엔드 포인트가 N값과 같을때 탈출

가장 기본적인 문제

문제 2

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

N의 값이 작아 O(nlogn)의 정렬을 사용해도 괜찮았음

문제 3

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

타겟을 정하기 위해 반복문을 순회하는 경우 O(N)이므로 좋은수를 하나 찾는 시간복잡도는 N^2 보단 작아야 할것
-> N^2의 경우에는 200^3
-> 좋은 수를 한개 찾는 시간복잡도는 최소 O(nlogn)이여야 함

핵심은 정렬된 데이터에서 자기 자신을 좋은 수 만들기에 포함하면 안됨!
-> 또한 타겟을 만드는 여러 조합이 있더라도 한가지 조합을 찾았더라면 바로 프로세스를 종료시켜야 함

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));
        int N = Integer.parseInt(br.readLine());
        long[] arr = new long[N];
        StringTokenizer st = new StringTokenizer(br.readLine());

        for(int i = 0; i < N; i++){
            arr[i] = Long.parseLong(st.nextToken());
        }

        Arrays.sort(arr);
        int answer = 0;

        for(int i = 0; i < N;i++){
            long target = arr[i];
            int startIndex = 0; int endIndex = N-1;

            while(startIndex < endIndex){
                // 0이 포함되어있거나, 타겟과 같은 값이 있는 경우에도 올바르게 값 출력 가능!
                if(arr[startIndex] + arr[endIndex] == target){
                    if(startIndex == i){
                        startIndex++;
                    }else if(endIndex == i){
                        endIndex++;
                    }else{
                        //둘이 다른 경우
                        answer++;
                        break;
                    }
                }else if(arr[startIndex] + arr[endIndex] < target){
                    startIndex++;
                }else{
                    // arr[startIndex] + arr[endIndex] > target
                    endIndex--;
                }
            }

        }
        System.out.println(answer);
        br.close();
    }
}

문제 4

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

간단한 문제이긴한데 누적합을 계산하면서 할려면... 인덱싱이 상당히 까다롭다

		while (end <= N) {
            if (sum >= target) {
                sum -= arr[start];
                start++;
            } else if (end == N) {
                break;
            } else {
                // sum < target
                sum += arr[end];
                end++;
            }

            if (sum == target) {
                answer++;
            }
        }

start와 end가 둘다 0일떄는 위와 같이 코드를 짜야됨 -> 아니면 에러 발생
: 위 로직 및 순서를 이해하자!

4-1) SUM >= M 인 경우, SUM을 줄여야 M에 가까워지므로, S 포인터를 1 증가 시킵니다. (오른쪽으로 한 칸 이동)

4-2) E 포인터가 끝 점에 도달했다면, S 포인터를 1 증가 시킵니다. (오른쪽으로 한 칸 이동)

4-3) SUM < M 인 경우, SUM을 늘리기위해 E 포인터를 1 증가 시킵니다.

4-4) SUM = M 인 경우, 하나 찾았으므로 count + 1 합니다.