[2531번] 회전 초밥 ( 슬라이딩 윈도우, 2차원 배열 메모리 초과 )

---

---

✅ 2차원 배열 메모리 초과

바로 앞에서 풀었던 문제에서 더 구현이 더해진 문제였다.
앞에꺼를 완전히 이해하고 풀어서, 이번 문제는 스무스하게 풀었다.
레벨을 차근차근 풀면서 느낀 점이 있다면,
낮은 레벨에서 풀었던 문제가 높은 레벨의 부분 문제가 된다는 점.
차곡차곡 실력이 쌓이는 것 같다.

이번엔 진짜 맞는데, 왜 틀렸지?

시간 복잡도도 O(n^2) 도 가능하다.
왜냐면 최악의 케이스가 30000*3000이기 때문에!

dArr 2차원 배열을 만들면서 메모리가 초과했나?? -> 정답

2차원 배열을 만들고 싶으면, 메모리부터 확인하자.
애초에 사용못하는 거를 인지하고 다른 방법을 사용할 수 있게!

👾
2차원 배열을 사용안해도 각 갯수를 1차원 배열에 넣고 결과값만 저장해놓으면 될 것 같은데 ?

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

public class Main {

	static int num[];
	static int dArr[][];
	static int cnt[];

	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st;
		st = new StringTokenizer(br.readLine());
		int n = Integer.parseInt(st.nextToken());
		int d = Integer.parseInt(st.nextToken());
		int k = Integer.parseInt(st.nextToken());
		int c = Integer.parseInt(st.nextToken());

		num = new int[n + k - 1];
		dArr = new int[n][d];
		cnt = new int[n];

		for (int i = 0; i < n; i++) {
			num[i] = Integer.parseInt(br.readLine());
		}

		for (int i = 0; i < k - 1; i++) {
			num[n + i] = num[i];
		}

		int start = 0;
		int end = 0;
		int j = 0;

		//쿠폰 번호를 dArr배열에 +1
		//30이면 29번째에 +1
		for (int i = 0; i < n; i++) {
			dArr[i][c - 1] = 1;
		}

		while (end < num.length) {
			end = start + k;
			//num배열을 슬라이딩 하면서 나온 값을 aArr[i][결과값] 1;
			for (int i = start; i < end; i++) {
				int result = num[i];
				dArr[j][result - 1]++; //0열 부터니까 num[i]-1이다.
			}
			start++;
			j++;
		}

		for (int row = 0; row < n; row++) {
			for (int col = 0; col < d; col++) {
				if (dArr[row][col] != 0) {
					cnt[row]++; //dArr배열에서 각 행에 따른 열의 값이 0이 아니면 ++
				}
			}
		}

		System.out.println(Arrays.stream(cnt).max().getAsInt());

	}
}

---

✅ 코드

배열을 1차원 배열을 만들고 바로 그 값을 저장시켰으니까
초기화를 while문 안에서 해줘야하고, 쿠폰 번호도 while문 안에서 선언해줘야 한다.

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

public class Main {

	static int num[];
	static int dArr[];
	static int cnt[];

	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st;
		st = new StringTokenizer(br.readLine());
		int n = Integer.parseInt(st.nextToken());
		int d = Integer.parseInt(st.nextToken());
		int k = Integer.parseInt(st.nextToken());
		int c = Integer.parseInt(st.nextToken());

		num = new int[n + k - 1];
		dArr = new int[d];
		cnt = new int[n];

		for (int i = 0; i < n; i++) {
			num[i] = Integer.parseInt(br.readLine());
		}

		for (int i = 0; i < k - 1; i++) {
			num[n + i] = num[i];
		}

		int start = 0;
		int end = 0;
		int j = 0;


		while (end < num.length) {
			dArr = new int[d]; //초기화를 여기서 해줘야!
			dArr[c - 1] = 1;//쿠폰 번호를 dArr배열에 +1 //30이면 29번째에 +1
			end = start + k;
			//num배열을 슬라이딩 하면서 나온 값을 aArr[i][결과값] 1;
			for (int i = start; i < end; i++) {
				int result = num[i];
				dArr[result - 1]++; //0열 부터니까 num[i]-1이다.
			}
			for (int i = 0; i < d; i++) {
				if (dArr[i] != 0) {
					cnt[j]++;
				}
			}
			start++;
			j++;
		}
		System.out.println(Arrays.stream(cnt).max().getAsInt());

	}
}

---

야호

---

✅ 슬라이딩 윈도우 범위

다시 앞으로 가야한다면, 아래 방법처럼 나눠줘도 괜찮을 것 같다.

int end = (i + k - 1) % n;