[JAVA] 투포인터, 슬라이딩 윈도우

투포인터 문제 - 두 배열의 공통 원소 출력

- 공통 원소를 추출해서 오름차순 출력하기

- 배열들을 미리 오름차순 정렬한다.

- 같은 값일 경우 둘 중에 아무거나 값을 넣고 둘 다 포인터 index를 증가시킨다.

- 더 작은 배열의 포인터 index를 증가시킨다.

- 첫 번째 배열이 더 큰 경우에 두 번째 배열 포인터 index++

- 두 번째 배열이 더 큰 경우에 첫 번째 배열 포인터 index++

import java.util.ArrayList;
import java.util.Arrays;

public class Solution {
    public static ArrayList<Integer> solution(int[] arr1, int[] arr2){
        ArrayList<Integer> answer = new ArrayList<>();

        Arrays.sort(arr1);
        Arrays.sort(arr2);

        int p1=0;
        int p2=0;
        int n = arr1.length;
        int m = arr2.length;

        while(p1<n && p2<m){
            if(arr1[p1]==arr2[p2]){ // 둘중에 값 아무거나 넣고, 둘다 idx증가
                answer.add(arr1[p1++]);
                p2++;
            } else if(arr1[p1]>arr2[p2]){ // 1번째 배열이 더 큰 경우 -> 작은 쪽을 증가 시키기
                p2++;
            } else {
                p1++;
            }
        }
        return answer;
    }

    public static void main(String[] args) {
        Solution T = new Solution();
        int[] arr1 = {1,3,9,5,2};
        int[] arr2 = {3,2,5,7,8};
        System.out.println(T.solution(arr1,arr2));
    }
}

 

 

슬라이딩윈도우 문제 - 연속된 K일의 최대 매출 구하기문제

- 수열에서 연속된 K개를 합했을 때, 합의 최대 값 구하기

- 일단 첫 번째부터 K번째 까지 값들을 다 더해줘서 max 값으로 지정한다.

- 그 이후로 k번째부터 배열의 마지막까지 반복문을 실행한다.

- sum = sum + 현재값 - 첫번째값

- 현재의 총합과 이전의 총합 중에서 최대 값으로 저장해준다.

- 배열을 종료 했을 때 나오는 최대 값이 수열에서 연속된 K개의 값들 중 최대 값이된다. 

public class Solution {
    public static int solution(int[] arr, int k){
        int answer = 0;
        int sum = 0;

        // 일단 맨 첫번째부터 k번째 값들을 다 더해준다.
        for(int i=0; i<k; i++){
            sum += arr[i];
        }
        answer = sum;

        // k부터 배열의 마지막까지 계산해본다.
        for(int i=k; i<arr.length; i++){
            sum+=(arr[i]-arr[i-k]); // 현재 값을 더해주고 맨 앞의 값을 지워준다.
            answer = Math.max(answer, sum); // 이전의 총합과 현재의 총합을 비교해줘서 최대값을 저장
        }

        return answer;
    }
    public static void main(String[] args) {
        Solution T = new Solution();
        int[] arr = {12,15,11,20,25,10,20,19,13,15};
        System.out.println(T.solution(arr, 3));
    }
}

 

복합적 문제 - 특정 숫자가 되는 경우의 수 구하기

- 투포인터는 O(N^2)에서 O(N)으로 개선 가능하다.

- N개의 수열에서 특정 숫자 M이 되는 경우의 수를 구해라

- N=8, M=6

- 수열 : 1 2 1 3 1 1 1 2

sum 1 -> 3 -> 4 -> 7 -> 6 -> 4...

// sum이 M보다 크면 lt를 빼주고 lt++
// sum이 M보다 작으면 rt++

for(int rt=0; rt<N; rt++){ // 1. 증가
    sum+= arr[rt]; // 2. 더하기
    if(sum==M) answer++; // 3. 확인

    // sum이 M보다 커지면 삭제
    while(sum>=M){
        sum -= arr[lt++];
        if(sum==M){
            answer++;
        }
    }
}

 

복합적 문제 - 연속으로 1인 수열의 최대 길이 출력

public class Solution {
    public static int solution(int[] arr, int k){
        int N = arr.length; // 길이는 : rt - lt + 1
        int count = 0, lt=0;
        int answer = 0;

        for(int rt=0; rt<arr.length; rt++){
            if(arr[rt]==0) count++;
            while(count>k){
                if(arr[lt]==0) count--;
                lt++;
            }
            answer = Math.max(answer, rt-lt+1);
        }

        return answer;
    }
    public static void main(String[] args) {
        Solution T = new Solution();
        int[] arr = {1,1,0,0,1,1,0,1,1,0,1,1,0,1};
        System.out.println(T.solution(arr, 2));
    }
}

 

Hash + 슬라이딩 윈도우 - N일 중에서 K일 동안 벌어들일 수 있는 매출액의 종류를 각 구간별로 구하기

public class Solution {
    public static ArrayList<Integer> solution(int[] arr){
        int n = 7;
        int k = 4;
        ArrayList<Integer> answer = new ArrayList<>();
        HashMap<Integer, Integer> HM = new HashMap<>();

        for(int i=0; i<k-1; i++){
            HM.put(arr[i], HM.getOrDefault(arr[i],0)+1);
        }
        int lt = 0;
        for(int rt=k-1; rt<n; rt++){
            HM.put(arr[rt], HM.getOrDefault(arr[rt],0)+1);
            answer.add(HM.size());
            HM.put(arr[lt], HM.get(arr[lt])-1);
            if(HM.get(arr[lt])==0) {
                HM.remove(arr[lt]);
            }
            lt++;
        }
        return answer;
    }
    public static void main(String[] args) {
        Solution T = new Solution();
        int[] arr = {20,12,20,10,23,17,10};
        System.out.println(T.solution(arr));
    }
}

 

Hash + 슬라이딩 윈도우 - 모든 아나그램 찾기

import java.util.HashMap;

public class Solution {
    public static int solution(String s, String t){
        int answer = 0;
        HashMap<Character, Integer> am = new HashMap<>();
        HashMap<Character, Integer> bm = new HashMap<>();

        for(char x : t.toCharArray()) bm.put(x, bm.getOrDefault(x,0)+1);
        int L = t.length()-1;
        for(int i=0; i<L; i++) am.put(s.charAt(i), am.getOrDefault(s.charAt(i), 0)+1);
        int lt = 0;
        for(int rt=L; rt<s.length(); rt++){
            am.put(s.charAt(rt), am.getOrDefault(s.charAt(rt), 0)+1);
            if(am.equals(bm)) answer++;
            am.put(s.charAt(lt), am.get(s.charAt(lt))-1);
            if(am.get(s.charAt(lt))==0) am.remove(s.charAt(lt));
            lt++;
        }

        return answer;
    }
    public static void main(String[] args) {
        Solution T = new Solution();
        String s = "bacaAacbaa";
        String t = "abca";
        System.out.println(T.solution(s,t));
    }
}