문제 풀이

문제를 본 순간 투포인터를 사용해야될 것 같다는 느낌이 들었다.
어떤 숫자가 몇번이 사용됐는지 체크하는 cnt배열을 사용하면 풀 수 있다.
l=0, r=0 부터 시작해서 r번째에 있는 숫자가 k번 미만으로 사용됐다면 이 숫자는 부분 수열에 포함되도 되기때문에 사용했다는 표시를 해주고 r을 늘려준다.
만약에 r이 이미 k번 사용됐다면 더 이상 늘려줄 수 없으므로 l을 오른쪽으로 이동시켜서 r번째에 있는 숫자가 k번 미만 사용이 될때 까지 부분수열을 줄여준다.
이런식으로 반복하면서 부분 수열의 최대 길이를 찾아주면된다.

문제 링크

boj/20922

소스코드

PS/20922.java

    import java.io.*;
    import java.util.*;


    public class Main {
        static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        static BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

        static int []arr;
        static int []cnt;
        public static void main(String[] args) throws IOException {
            StringTokenizer st = new StringTokenizer(br.readLine());
            int n = Integer.parseInt(st.nextToken());
            int k = Integer.parseInt(st.nextToken());
            arr = new int[n];
            cnt = new int[100001];
            st = new StringTokenizer(br.readLine());
            for(int i=0;i<n;i++)
                arr[i] = Integer.parseInt(st.nextToken());

            int l =0, r= 0;
            int ans = 0 ;
            while(l<=r)
            {
              if(r<=n-1 &&cnt[arr[r]] <k)
              {
                  cnt[arr[r]]++;
                  r++;

              }
              else if(cnt[arr[r]] == k)
              {
                  cnt[arr[l]]--;
                  l++;
              }

                ans = Math.max(ans, r - l);
                if(r == n)
                    break;
            }
            System.out.println(ans);
        }

    }
    }