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

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

리스트 완전 탐색 시 성능이 좋지 않을 때 적용할만한 알고리즘이다.

• 투포인터 : 리스트에서 두 개의 포인터를 조작하여 원하는 결과를 얻는 방식의 알고리즘. O(n)의 성능을 낸다.
• 슬라이딩 윈도우 : 고정 크기의 윈도우가 이동하면서 원하는 결과를 얻는 방식의 알고리즘. 처음 윈도우만 계산한 뒤 윈도우를 이동시킨다. 이동시킬때 이전 윈도우의 값을 조작한다. O(n)의 성능을 낸다.

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

투포인터

투포인터 관련 문제이다. https://www.acmicpc.net/problem/1806

1806번: 부분합

import java.io.IOException;
import java.util.*;
import java.lang.*;
import java.io.BufferedReader;
import java.io.InputStreamReader;

public class Main {

    static int N, S;
    static int[] arr;

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine(), " ");

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

        int start = 0, end = 0; //투포인터
        int answer = 100000;
        int sum = arr[0]; //start부터 end까지의 합

        while(start <= end) {
            if(sum < S) {
                end++;
                if(end < N) sum += arr[end];
                else break;
            }
            else{
                answer = Math.min(answer, end-start+1);
                sum -= arr[start];
                start++;
            }
        }

        if(answer == 100000) System.out.print(0);
        else System.out.print(answer);
    }
}

슬라이딩 윈도우

슬라이딩 윈도우 관련 문제이다. https://www.acmicpc.net/problem/2531

2531번: 회전 초밥

import java.io.IOException;
import java.util.*;
import java.lang.*;
import java.io.BufferedReader;
import java.io.InputStreamReader;

public class Main {

    static int n,d,k,c;
    static int answer, result;
    static int[] conveyorBelt;
    static int[] visit;

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine(), " ");

        n = Integer.parseInt(st.nextToken());
        d = Integer.parseInt(st.nextToken());
        k = Integer.parseInt(st.nextToken());
        c = Integer.parseInt(st.nextToken());
        conveyorBelt = new int[n];
        visit = new int[d+1];

        for(int i=0; i<n; i++) {
            int sushi = Integer.parseInt(br.readLine());
            conveyorBelt[i] = sushi;
        }

        //처음 윈도우 계산
        for(int i=0; i<k; i++) {
            if (visit[conveyorBelt[i]] == 0) result += 1;
            visit[conveyorBelt[i]] += 1;
        }
        if(visit[c] == 0) answer = result + 1;
        else answer = result;

        //윈도우를 이동하면서 동작
        for(int i=0; i<n; i++) {
            int start = i;
            int end = (start + k) % n;

            visit[conveyorBelt[start]] -= 1;
            if (visit[conveyorBelt[start]] == 0) result -= 1;

            if (visit[conveyorBelt[end]] == 0) result += 1;
            visit[conveyorBelt[end]] += 1;

            if (visit[c] == 0) answer = Math.max(answer, result + 1);
            else answer = Math.max(answer, result);
        }
        System.out.print(answer);
    }
}