효율성[O(n2) -> O(n)] 섹션 - (1)

📍 섹션 3.Two pointers, sliding window [효율성 O(n2) -> O(n)]

효율성[O(n2) -> O(n)] 섹션 - (1)

3-1. 두 배열 합치기 | Two Pointers 알고리즘 사용

/* 3-1. 두 배열 합치기
[설명] 효율성 
오름차순으로 정렬이 된 두 배열이 주어지면 두 배열을 오름차순으로 합쳐 출력하는 프로그램을 작성하세요.
*/
public class Main1 {
    //솔루션 함수 
    public ArrayList<Integer> solution(int n, int m, int[]a, int[]b) {
        ArrayList<Integer> answer = new ArrayList<>();
        int p1 =0, p2 = 0; //두 개의 포인터 선언
        //각각 지칭할 배열 크기 안에서만 돌도록 조건 넣고 
        while(p1 < n && p2 <m) {
            if(a[p1] < b[p2]) {
                answer.add(a[p1++]); //먼저 a[p1] 넣고 p1++ 된다.
            }else{
                answer.add(b[p2++]);
            }
        }
        //어떤 지칭 p가 나왔으면. 이제 남은 애들 answer에 누적시키기 위해
        //각각의 남은 경우 대비해서 add 처리 
        while(p1<n) answer.add(a[p1++]);
        while(p2<m) answer.add(b[p2++]);

        return answer;
    }
    //실행 메인 
    public static void main(String[] args) {
        // TODO Auto-generated method stub
        Main1 T = new Main1();
        Scanner kb = new Scanner(System.in);

        //입력
        int n = kb.nextInt();
        int[] a = new int[n];
        for(int i = 0; i<n; i++) {
            a[i] = kb.nextInt();
        }
        int m = kb.nextInt();
        int[] b = new int[m];
        for(int i = 0; i<m; i++) {
            b[i] = kb.nextInt();
        }
        //출력 
        for(int x : T.solution(n, m, a, b)) {
            System.out.print(x + " ");
        }
    }
}

3-2.공통원소 구하기 | Two Pointers 알고리즘 사용

/* 3-2 공통원소 구하기 (교집합-> 오름차순)
 A, B 두 개의 집합이 주어지면 두 집합의 공통 원소를 추출하여 오름차순으로 출력하는 프로그램을 작성하세요.
*/
public class Main2 {
    //솔루션 함수 
    public ArrayList<Integer> solution(int n, int m, int[]a, int[]b){
        ArrayList<Integer> answer = new ArrayList<>();
        int p1 = 0, p2 = 0;
        //1) 먼저 두 배열 오름차순 정렬 시킬 것 
        Arrays.sort(a);
        Arrays.sort(b);

        //2) 공통원소 담기 (한 배열 끝나면 끝. 교집합만 구하는 거기 때문)
        while(p1 < n && p2 <m) {
            if(a[p1] == b[p2]) {
                answer.add(a[p1++]); //같은 애 둘 중 하나만 담음 
                p2++;
            }else if(a[p1] < b[p2]) {
                p1++; //더 작은 애의 포인터만++
            }else {
                p2++; //더 작은 애의 포인터만++
            }
        }
        return answer;
    }
    //실행 메인 
    public static void main(String[] args) {
        // TODO Auto-generated method stub
        Main2 T = new Main2();
        Scanner kb = new Scanner(System.in);
        //입력
        int n = kb.nextInt();
        int[] a = new int[n];
        for(int i = 0; i<n; i++) {
            a[i] = kb.nextInt();
        }

        int m = kb.nextInt();
        int[] b = new int[m];
        for(int i = 0; i<m; i++) {
            b[i] = kb.nextInt();
        }

        //출력
        for(int x : T.solution(n, m, a, b)) {
            System.out.print(x + " ");
        }    
    }
}

3-3. 최대 매출 | sliding window 알고리즘 사용

import java.util.Scanner;

/* 3-3. 최대 매출 (sliding window 알고리즘 사용)
[입력]
첫 줄에 N(5<=N<=100,000)과 K(2<=K<=N)가 주어집니다.
두 번째 줄에 N개의 숫자열이 주어집니다. 각 숫자는 500이하의 음이 아닌 정수입니다.
[출력]
첫 줄에 최대 매출액 출력 
*/
public class Main3 {
    //솔루션 함수 
    public int solution(int n, int k, int[] arr) {
        int answer = 0, sum = 0;

        //최초의 연속3개 합 세팅해놈
        for(int i =0; i < k; i++) {
            sum += arr[i];
        }
        answer = sum; //일단 초기화 저장시켜놓고 

        //sliding window
        //남은 뒷부분을 다시 for 돌면서 창 밀고 나가고 (민 만큼 앞 부분 빼고)
        for(int i = k; i<n; i++) {
            sum += (arr[i] - arr[i-k]); //민 만큼 더하고 (밀린 부분 빼고)
            answer = Math.max(answer, sum); //더 큰 값으로 세팅 
        }
        return answer;
    }
    //실행 메인
    public static void main(String[] args) {
        // TODO Auto-generated method stub
        Main3 T = new Main3();
        Scanner kb = new Scanner(System.in);
        //입력 
        int n = kb.nextInt();
        int k = kb.nextInt();

        int[] arr = new int[n];

        for(int i = 0; i<n; i++) {
            arr[i] = kb.nextInt();
        }
        //출력 
        System.out.println(T.solution(n, k, arr));

    }
}

3-4. 연속 부분수열 | 복합적 문제 *어려움**

• lt, rt 두 개의 포인터로 (구간 찍음)
• 1) sum < m 작은 동안에는 구간 rt ++, sum에 누적시킴
• 2) sum >= m 크거나 같은 동안에는 구간 lt++ , 기존 lt 지칭 값은 sum에서 빼줌

import java.util.Scanner;

/* 3-4. 연속 부분수열 
[입력]
첫째 줄에 N(1≤N≤100,000), M(1≤M≤100,000,000)이 주어진다.
[출력]
첫째 줄에 경우의 수를 출력한다.
*/
public class Main4 {

    //솔루션 함수 
    public int solution(int n, int m, int[] arr) {
        int answer = 0;
        //lt = 0 찍어놓고 
        int lt = 0, sum = 0;
        //rt 확장시키면서 그 구간의 sum을 비교 m과 비교함
        for(int rt = 0; rt <n; rt++) {
            sum += arr[rt];
            if(sum == m) answer++;
            //for이 아니라 while을 돌리는 이유
                //[11115] 일 경우 sum==6될때까지 lt가 연속 증가 가능하도록 
            while(sum >= m) {
                sum -= arr[lt++];
                if(sum == m) answer++;
            }
        }
        return answer;
    }
    //실행 메인 
    public static void main(String[] args) {
        // TODO Auto-generated method stub
        Main4 T = new Main4();
        Scanner kb = new Scanner(System.in);

        int n = kb.nextInt();
        int m = kb.nextInt();

        int[] arr = new int[n];
        for(int i = 0; i<n; i++) {
            arr[i] = kb.nextInt();
        }

        System.out.println(T.solution(n, m, arr));
    }
}