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

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

20922번: 겹치는 건 싫어

[문제]

홍대병에 걸린 도현이는 겹치는 것을 매우 싫어한다. 특히 수열에서 같은 원소가 여러 개 들어 있는 수열을 싫어한다. 도현이를 위해 같은 원소가 K개 이하로 들어 있는 최장 연속 부분 수열의 길이를 구하려고 한다.

 100000 이하의 양의 정수로 이루어진 길이가 N인 수열이 주어진다.  이 수열에서 같은 정수를 K개 이하로 포함한 최장 연속 부분 수열의 길이를 구하는 프로그램을 작성해보자.

 

[입력 조건]

• 첫째 줄에 정수 N (1≤ N ≤ 200,000)과 K (1≤ K ≤100)가 주어진다.
• 둘째 줄에는 a1, a2, .... , an이 주어진다 (1 ≤ ai ≤100000)

 

[코드]

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

public class BaekJoon_20922 {
	
 	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[] num=new int[n];
		int[] count=new int[100001]; // 각 수가 몇번 나왔는지 저장한 배열
		st=new StringTokenizer(br.readLine());
		for(int i=0;i<n;i++)
			num[i]=Integer.parseInt(st.nextToken());
		
		int start=0,end=0;
		int result=0;
		while(end<n) {
			/*
			 * 수열 늘리기
			 * end가 가리키고 있는 수가 아직 k번 등장하지 않았을 경우 추가 가능
			 */
			while(end<n&&count[num[end]]+1<=k) {
				count[num[end]]++; // 등장 횟수 증가
				end++;
			}
				
			int length=end-start; // 수열의 길이
			result=Math.max(result, length);
			
			// 시작 포인트 증가
			count[num[start]]--;
			start++;
		}
		
		System.out.println(result);
	}

}

 

[고찰]

 이번 문제는 최근 많이 풀어봤던 투포인터 알고리즘을 사용해야 했다. 한 숫자의 k개의 중복만을 허용하는 최장 수열을 구해야 하므로 각 숫자의 등장 횟수를 저장하는 배열을 사용하는 부분이 가장 중요했다. 어떤 수도 등장 횟수가 k를 초과하지 않을 때 까지 end 포인트를 늘려주면서 수열을 늘려준 뒤 수열의 길이의 최댓값을 갱신하고, 이후 start 포인트를 감소하여 해당 과정을 반복한다.