[문제풀이] 쿠키구입

업데이트:

문제 링크 : 쿠키구입

풀이 시간 : 30분

1. 문제 풀이

미리 배열의 누적 값을 구해서 탐색하는 문제

1) 각 위치 별 쿠키의 누적 개수를 저장

2) 각 위치를 돌면서 첫째가 갖을 수 있는 개수와 둘째가 갖을 수 있는 개수를 비교

3) 적절한 조건을 통해서 효율성 높임

3-1) 한명이 최대한 갖을 수 있는 쿠키 수(전체 쿠키 수의 절반)를 이용하여 넘어가는 경우 스킵

3-2) 첫째가 갖는 경우가 현재 최대 값보다 작으면 스킵(둘째의 쿠키 수 계산 X)

2. 소스 코드

    public int solution(int[] cookie) {
        int answer = 0;
		int len = cookie.length;
		int[] sum = new int[len];
		sum[0] = cookie[0];
		// 각 위치까지의 누적 쿠키 개수
		for (int i = 1; i < len; i++) {
			sum[i] = sum[i - 1] + cookie[i];
		}
		// 한명이 가질 수 있는 최대 쿠키 수
		int mid = sum[len - 1] / 2;
		for (int i = 0; i < sum.length; i++) {
			for (int j = i; j >= 0; j--) {
				//첫째 아들이 받는 쿠키
				int pivot = sum[i] - sum[j] + cookie[j];
				// 최대 값보다 작을 때
				if(answer>= pivot) {
					continue;
				}
				// 한명이 가질 수 있는 최대 개수를 넘긴 경우
				if (mid < pivot) {
					break;
				}
				// 두번째 아들이 받는 쿠키
				for (int k = i + 1; k < len; k++) {
					int temp = sum[k] - sum[i];
					// 첫째보다 많거나 같을 경우
					if (pivot <= temp) {
						// 같으면 현재 최대값과 비교
						if (pivot == temp) {
							answer = Math.max(answer, pivot);
						}
						break;
					}
				}

			}
		}
		return answer;
    }

3. 후기

쿠키의 누적을 미리 계산을 하여 아들들이 갖는 쿠키의 수를 빠르게 계산한다

이를 이용한 정렬 방법인 Count sorting이 있는데 입력값이 특정 조건을 만족하면 정렬의 속도는 O(n)이 된다.

참고