[백준 20922번] 겹치는 건 싫어

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

package datastructure;

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;

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

        int N = Integer.parseInt(st.nextToken());
        int K = Integer.parseInt(st.nextToken());

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

        int left = 0;
        int right = 0;
        int answer = 0;

        while (left < N && right < N) {
            if (visit[arr[right]] < K) {
                visit[arr[right]]++;
                right++;
                answer=Math.max(answer, right-left);
            } else {
                visit[arr[left]]--;
                left++;
            }
        }
        System.out.println(answer);

    }
}

 

투 포인터 문제다! 조금만 관점을 바꾸면 쉽게 풀 수 있는 문제다. 초반에는 연속 부분 수열 개념을 이해하는 데 시간이 좀 걸렸지만, 결국 해결했다 ㅋㅋㅋ.

투 포인터 문제이기 때문에 left와 right 또는 start와 end 변수를 활용하면 쉽게 접근할 수 있다.

이 문제의 핵심은 수열을 따라가면서 Math.max를 활용해 현재까지의 길이를 갱신하는 것이다. 만약 K를 초과하는 경우가 발생하면, left 포인터가 가리키는 부분부터 방문한 값을 제거하면서 조건을 만족하도록 만든다. 이런 방식으로 진행하면 최종적으로 정답을 구할 수 있다.