백준 30804번 : 과일 탕후루 (슬라이딩 윈도우)

1. 문제

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

 

은하는 긴 막대에 N$N$개의 과일이 꽂혀있는 과일 탕후루를 만들었습니다. 과일의 각 종류에는 1$1$부터 9$9$까지의 번호가 붙어있고, 앞쪽부터 차례로 S1,S2,⋯,SN$S_1, S_2, \cdots, S_N$번 과일이 꽂혀있습니다. 과일 탕후루를 다 만든 은하가 주문을 다시 확인해보니 과일을 두 종류 이하로 사용해달라는 요청이 있었습니다.

탕후루를 다시 만들 시간이 없었던 은하는, 막대의 앞쪽과 뒤쪽에서 몇 개의 과일을 빼서 두 종류 이하의 과일만 남기기로 했습니다. 앞에서 a$a$개, 뒤에서 b$b$개의 과일을 빼면 Sa+1,Sa+2,⋯,SN−b−1,SN−b$S_{a+1}, S_{a+2}, \cdots, S_{N-b-1}, S_{N-b}$번 과일, 총 N−(a+b)$N-(a+b)$개가 꽂혀있는 탕후루가 됩니다. (0≤a,b;$(0 \le a, b;$ a+b<N)$a+b < N)$ 

이렇게 만들 수 있는 과일을 두 종류 이하로 사용한 탕후루 중에서, 과일의 개수가 가장 많은 탕후루의 과일 개수를 구하세요.

입력

첫 줄에 과일의 개수 N$N$이 주어집니다. (1≤N≤200000)$(1 \le N \le 200\,000)$ 

둘째 줄에 탕후루에 꽂힌 과일을 의미하는 N$N$개의 정수 S1,⋯,SN$S_1, \cdots, S_N$이 공백으로 구분되어 주어집니다. (1≤Si≤9)$(1 \le S_i \le 9)$ 

출력

문제의 방법대로 만들 수 있는 과일을 두 종류 이하로 사용한 탕후루 중에서, 과일의 개수가 가장 많은 탕후루의 과일 개수를 첫째 줄에 출력하세요.

2. 코드

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

public class Main {

	public static void main(String[] args) throws NumberFormatException, IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		int N = Integer.parseInt(br.readLine());
		String[] splits = br.readLine().split(" ");
		int[] list = new int[N];
		for (int i = 0; i < N; i++) {
			list[i] = Integer.parseInt(splits[i]);
		}
		for (int i = N; i > 1; i--) {
			boolean success = false;
			for (int j = 0; j <= N - i; j++) {
				int n1 = 0, n2 = 0;
				boolean fail = false;
				for (int k = 0; k < i; k++) {
					int num = list[j + k];
					if (n1 == 0) n1 = num;
					if (num != n1 && n2 == 0) n2 = num;
					if (num != n1 && num != n2) {
						fail = true;
						break;
					}
				}
				if (!fail) {
					success = true;
				}
			}
			if (success) {
				System.out.println(i);
				break;
			}
		}
	}
	
}

3. 해설

• 범위를 점점 줄여가면서 숫자가 두개뿐인 조건을 만족하는지 확인 후 종료
• 문제 : 최악의 경우 시간 복잡도가 O(N^2) 으로 비효율 적이다
  → 슬라이딩 윈도우 알고리즘을 사용하여 O(N)으로 변경해야한다

4. 개선된 풀이

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

public class Main {

	public static void main(String[] args) throws NumberFormatException, IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		int N = Integer.parseInt(br.readLine());
		String[] splits = br.readLine().split(" ");
		int[] list = new int[N];
		for (int i = 0; i < N; i++) {
			list[i] = Integer.parseInt(splits[i]);
		}
		int[] count = new int[10];
		int distinct = 0;
		int left = 0;
		int maxLen = 0;
		for (int right = 0; right < N; right++) {
			if (count[list[right]] == 0) {
				distinct++;
			}
			count[list[right]]++;
			while (distinct > 2) {
				count[list[left]]--;
				if (count[list[left]] == 0) {
					distinct--;
				}
				left++;
			}
			maxLen = Math.max(maxLen, right - left + 1);
		}
		System.out.println(maxLen);
	}
	
}

• 각각의 과일을 카운팅하는 배열을 만들고, 새로운 과일을 만날때 (즉, 카운팅 배열의 값이 0일때) distinct 값을 올린다
• distinct 값이 3이상이라면 left를 올려서 윈도우 범위를 좁히고 distinct가 2가 될때까지 left를 당긴다
• 이외 상황에서는 계속 right를 올려서 윈도우 범위를 늘리고, 매 반복마다 maxLen을 동기화한다