백준 20922번 : 겹치는 건 싫어

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

20922번: 겹치는 건 싫어

 

 

 

 

 

 

문제

• 같은 원소가 K개 이하로 들어있는 최장 연속 부분 수열 길이 구하기

 

 

제한사항

• N ≤ 20만

 

 

 

 

 

풀이

 가능한 모든 구간의 시작점과 끝점을 2중 for문을 통해 구하고, 안에 있는 원소들의 개수를 카운트할 수 도 있다. 하지만 배열의 길이가 최대 20만으로, O(N^2)의 알고리즘으로 푼다면 시간 초과가 날 것이다.

 

그러므로 O(N^2) 미만으로 구간을 구할 수 있도록, 투포인터 알고리즘을 사용하여 탐색한다.

 

최장 연속 부분 수열에서 같은 원소가 K개 이하로 들어있는지 확인해야 한다. 구간의 시작점과 끝점을 모두 0번째에서 시작해, 원소의 개수에 따라 포인터를 이동해주면 된다.

 

 

•  원소 별 개수 저장하기

 int형의 배열을 선언해, 해당 원소를 배열의 인덱스로하고, 해당 값에는 개수를 저장해준다. 문제에서 100000 이하의 양의 정수로 이루어진 수열이라고 했으므로, 100001 길이의 배열을 선언해주면 된다.

 

 

 

• 투포인터

 처음에는 오른쪽 포인터를 하나씩 늘려가며, 원소의 개수에 따라 왼쪽 포인터를 늘려줬다. 왼쪽 포인터 조정이 끝나고 나면, 구간의 길이를 계산해 max 값을 갱신해주었다. 하지만 모든 테스트케이스를 통과하지 못한다.

 

 

int[] count = new int[1000001];
int right = 0;
int max = 0;
		
for(int left = 0; left < N; left++) {
	while(right < N && count[arr[right]] < K) {
		count[arr[right]]++;
		right++;
	}
			
	max = Math.max(max, right - left);
	count[arr[left]]--;
}

 

 

 

반례

10 3
1 1 1 2 2 1 1 1 1 1

output : 5

 

 

 

 반대로 왼쪽 포인터를 하나씩 늘려가며, 오른쪽 포인터는 원소의 개수에 따라 늘려줬다. 이렇게 했더니 모든 테스트 케이스를 통과한다.

 

 

 

 

 

코드

package algorithm;

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

public class BOJ_겹치는건싫어 {

	public static void main(String[] args) throws Exception {
		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];
		
		st = new StringTokenizer(br.readLine());
		for(int i = 0; i < N; i++) {
			arr[i] = Integer.parseInt(st.nextToken());
		}
		
		//구현
		int[] count = new int[1000001]; //원소별 개수 저장
		int right = 0;
		int max = 0; //정답: 최장 연속 부분 수열의 길이
		
		for(int left = 0; left < N; left++) { //왼쪽은 하나씩 옮김
			while(right < N && count[arr[right]] < K) { //K개 미만일때까지 오른쪽으로 옮김
				count[arr[right]]++;
				right++;
			}
			
			max = Math.max(max, right - left); //최댓값 갱신
			count[arr[left]]--; //왼쪽 원소의 수 빼주기
		}
		
		System.out.println(max);
	}

}

 

 

 

 

 

 

결과

 

 

 

 

 

배운점