boj 2632: 피자판매

앞선 글들과 마찬가지 방법으로 풀었는데 12%에서 시간 초과가 나서

아래와 같이 바이너리 서치 방법으로 풀었는데 75% 대에서 다시 시간초과가 났다.

 

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

public class Main {
	public static void main(String[] args) {
		Scanner in = new Scanner(System.in);
		int size = in.nextInt();
		int m = in.nextInt();
		int n = in.nextInt();
		int A[] = new int[m];
		int B[] = new int[n];

		int aSum = 0;
		for (int i = 0; i < m; i++) {
			A[i] = in.nextInt();
			aSum += A[i];
		}
		int bSum = 0;
		for (int i = 0; i < n; i++) {
			B[i] = in.nextInt();
			bSum += B[i];
		}

		ArrayList<Integer> aPizza = new ArrayList<Integer>();
		ArrayList<Integer> bPizza = new ArrayList<Integer>();

		findAllSums(A, aPizza);
		findAllSums(B, bPizza);
		aPizza.add(aSum);
		bPizza.add(bSum);

		Collections.sort(aPizza);
		Collections.sort(bPizza);

		long ans = 0;
		for (int sum : aPizza) {
			int cnt = binarySearch(bPizza, size - sum);

			if (cnt != -1) {
				ans += cnt;
			}
		}

		System.out.println(ans);
	}

	public static int binarySearch(ArrayList<Integer> list, int target) {
		int left = 0;
		int right = list.size() - 1;
		int mid = (left + right) / 2;
		while (left <= right) {
			mid = (left + right) / 2;

			if (target == list.get(mid)) {
				break;
			} else if (target < list.get(mid)) {
				right = mid - 1;
			} else {
				left = mid + 1;
			}
		}

		if (target == list.get(mid)) {
			int ans = 1;
			int index = mid - 1;
			while (index >= 0) {
				if (target == list.get(index)) {
					ans++;
				} else {
					break;
				}
				index--;
			}
			index = mid + 1;
			while (index < list.size()) {
				if (target == list.get(index)) {
					ans++;
				} else {
					break;
				}
				index++;
			}
			return ans;
		}

		return -1;
	}

	public static void findAllSums(int arr[], ArrayList<Integer> list) {
		int length = arr.length;
		
		for (int i = 0; i < length; i++) {
			int sum = 0;
			int index = i;
			while (true) {
				sum += arr[index % length];
				list.add(sum);
				index++;

				if (index - i + 1 == length) {
					break;
				}
			}
		}
		list.add(0);

		return;
	}
}

 

LinkedList에서의 데이터의 삽입, 삭제 시에는 ArrayList와 비교해 굉장히 빠른데,

LinkedList는 이전 노드와 다음 노드를 참조하는 상태만 변경하면 되기 때문이다.

삽입, 삭제가 일어날 때 O(1)의 시작 복잡도를 가진다.

반면 ArrayList의 경우 삽입, 삭제 이후 다른 데이터를 복사해야 하기 때문에 최악의 경우 O(N) 의 성능을 내게 된다.

그래서 LinkedList로 바꿨는데 그래도 시간초과는 똑같음

 

이진 탐색에서 시간이 걸리는 것 같아서 HashMap에 나올 수 있는 피자의 넓이를 넣어놓고 바로 가져올 수 있도록 바꿨다.

import java.util.*;

public class Main {
	public static void main(String[] args) {
		Scanner in = new Scanner(System.in);
		int size = in.nextInt();
		int m = in.nextInt();
		int n = in.nextInt();
		int A[] = new int[m];
		int B[] = new int[n];

		int aSum = 0;
		for (int i = 0; i < m; i++) {
			A[i] = in.nextInt();
			aSum += A[i];
		}
		int bSum = 0;
		for (int i = 0; i < n; i++) {
			B[i] = in.nextInt();
			bSum += B[i];
		}

		HashMap<Integer, Integer> aPizza = new HashMap<Integer, Integer>();
		HashMap<Integer, Integer> bPizza = new HashMap<Integer, Integer>();

		findAllSums(A, aPizza);
		findAllSums(B, bPizza);

		aPizza.put(aSum, 1);
		bPizza.put(bSum, 1);
		aPizza.put(0, 1);
		bPizza.put(0, 1);

		long ans = 0;

		for (int sum : aPizza.keySet()) {
			int cnt = bPizza.getOrDefault(size - sum, -1);
			if (cnt != -1) {
				ans += cnt * aPizza.get(sum);
			}
		}

		System.out.println(ans);
	}

	public static void findAllSums(int arr[], HashMap<Integer, Integer> list) {
		int length = arr.length;

		for (int i = 0; i < length; i++) {
			int sum = 0;
			int index = i;
			while (true) {
				sum += arr[index % length];
				list.putIfAbsent(sum, 0);
				list.replace(sum, list.get(sum) + 1);
				index++;

				if (index - i + 1 >= length) {
					break;
				}
			}
		}
		return;
	}
}