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

문제

 

 

접근 방식

길이가 N인 수열에서 같은 숫자끼리는 최대 K번까지만 사용한 부분 수열을 구해야 한다.

 

각 숫자들마다 등장 횟수를 기록해야하기 때문에 불리언 배열이 아닌

정수형 배열에 특정 숫자가 등장 할 때마다 해당 인덱스에 카운트를 증가시키면서

투 포인터로 탐색을 하다가 특정 숫자가 K번 이미 등장 했을 때 또 등장했다면

만들 수 있는 부분 수열의 끝이므로 현재 부분 수열의 길이를 구한 후에

현재 까지 가장 긴 부분 수열의 길이인지 비교하고 값을 바꿔주면 된다. 

 

풀이

public class Main {

	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[] useCount = new int[200_001];

		st = new StringTokenizer(br.readLine());

		for (int i = 0; i < n; i++) {
			arr[i] = Integer.parseInt(st.nextToken());
		}

		int end = 0;
		int max = 0;

		for (int start = 0; start < n; start++) {
			while (end < n) {
				if (useCount[arr[end]] == k) break;
				useCount[arr[end++]]++;
			}

			max = Math.max(max, end - start);

			useCount[arr[start]]--;
		}

		System.out.println(max);
	}
}