백준_15961 회전 초밥(자바) / 슬라이딩 윈도우

시간 & 메모리 제한

문제

입력 & 출력

 - 아 왜......... 메모리 초과

바로 아래 코드는 메모리 초과 코드에요...

package com.Back;

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.StringTokenizer;

public class Back_15961 {
	static int N,d,k,c,ans=0;
	static int[] arr;
	static int[][] arr2;
	static boolean[] identify;
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine());
		N = Integer.parseInt(st.nextToken());
		d = Integer.parseInt(st.nextToken());
		k = Integer.parseInt(st.nextToken());
		c = Integer.parseInt(st.nextToken());
		arr = new int[N];
		arr2 = new int[N][k+1];
		for (int i = 0; i < N; i++) {
			arr[i]=Integer.parseInt(br.readLine());					
		}
		for (int i = 0; i < N; i++) {
			arr2[i][k]=c;
		}
		for (int i = 0; i < N; i++) {
			for (int j = 0; j < k; j++) {
				int temp = (i+j)%N;
				arr2[i][j]=arr[temp];
			}
		}
		for (int i = 0; i < N; i++) {
			int temp=0;
			Arrays.sort(arr2[i]);
			
			identify = new boolean[d];
			for (int j = 0; j < k+1; j++) {
				identify[arr2[i][j]-1]=true;
			}
			
			for (int j = 0; j < d; j++) {
				if(identify[j]==true) {
					temp++;
				}  
			}
			ans = ans> temp? ans : temp;
		}

		System.out.println(ans);
	}
}

- 문제를 보니까 N의 갯수는 최대 300만개 였고, 이중 for문을 돌려서 찾으니까 300만 ^ 2 의 시간 복잡도를 가지므로, 시간적으로 엄청 많이 들어갑니다.... 

슬라이딩 윈도우로 푸니까 맞았습니다..

슬라이딩 윈도우를 통한 문제풀이

package com.Back;

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

public class Back_15961 {
	//접시의 수, 초밥의 가짓수, 연속해서 먹는 접시수, 쿠폰번호
	static int N,d,k,c,ans=0;
	static int arr[],visited[];
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine());
		N = Integer.parseInt(st.nextToken());
		d = Integer.parseInt(st.nextToken());
		k = Integer.parseInt(st.nextToken());
		c = Integer.parseInt(st.nextToken());
		arr = new int[N];
		visited = new int[d+1];
		for (int i = 0; i < N; i++) {
			arr[i]=Integer.parseInt(br.readLine());
		}
		slide();
		System.out.println(ans);
	}
	private static void slide() {
		int total=0;
		for (int i = 0; i < k; i++) {
			if(visited[arr[i]] ==0) total++;
			visited[arr[i]]++;
		}
		ans = total;
		
		for (int i = 1; i < N; i++) {
			if(ans<=total) {
				if(visited[c]==0) {
					ans = total+1;
				}else {
					ans = total;
				}
			}
			//
			visited[arr[i-1]]--;
			if(visited[arr[i-1]]==0)total--;
			
			if(visited[arr[(i+k-1)%N]]==0)total++;
			visited[arr[(i+k-1)%N]]++;
		}
	}
}

 

 

- 아래와 같이 슬라이딩 윈도우는 한칸씩 옮겨 가면서 값을 찾는 것을 말한다.

- 위 그림은 8개씩 묶어서 값을 얻어야 하는 경우에 대한 그림을 그린 것이다...

 

- 이 처럼 슬라이딩 윈도우를 구현하기 위해서 처음 k개 만큼을 배열에 담아준다.

 

- 그리고 k개의 배열을 담은 이후에 체크하고, 그 이후 하나를 빼고 하나를 더해주는 방식으로 문제를 해결하면 됩니다.