Codility_Peaks

10-4. Peaks

A non-empty array A consisting of N integers is given.

A peak is an array element which is larger than its neighbors. More precisely, it is an index P such that 0 < P < N − 1, A[P − 1] < A[P] and A[P] > A[P + 1].

For example, the following array A:

A[0] = 1
A[1] = 2
A[2] = 3
A[3] = 4
A[4] = 3
A[5] = 4
A[6] = 1
A[7] = 2
A[8] = 3
A[9] = 4
A[10] = 6
A[11] = 2

has exactly three peaks: 3, 5, 10.

We want to divide this array into blocks containing the same number of elements. More precisely, we want to choose a number K that will yield the following blocks:

A[0], A[1], ..., A[K − 1],
A[K], A[K + 1], ..., A[2K − 1],
...
A[N − K], A[N − K + 1], ..., A[N − 1].
What's more, every block should contain at least one peak. Notice that extreme elements of the blocks (for example A[K − 1] or A[K]) can also be peaks, but only if they have both neighbors (including one in an adjacent blocks).

The goal is to find the maximum number of blocks into which the array A can be divided.

Array A can be divided into blocks as follows:

one block (1, 2, 3, 4, 3, 4, 1, 2, 3, 4, 6, 2). This block contains three peaks.
two blocks (1, 2, 3, 4, 3, 4) and (1, 2, 3, 4, 6, 2). Every block has a peak.
three blocks (1, 2, 3, 4), (3, 4, 1, 2), (3, 4, 6, 2). Every block has a peak. Notice in particular that the first block (1, 2, 3, 4) has a peak at A[3], because A[2] < A[3] > A[4], even though A[4] is in the adjacent block.
However, array A cannot be divided into four blocks, (1, 2, 3), (4, 3, 4), (1, 2, 3) and (4, 6, 2), because the (1, 2, 3) blocks do not contain a peak. Notice in particular that the (4, 3, 4) block contains two peaks: A[3] and A[5].

The maximum number of blocks that array A can be divided into is three.

Write a function:

class Solution { public int solution(int[] A); }

that, given a non-empty array A consisting of N integers, returns the maximum number of blocks into which A can be divided.

If A cannot be divided into some number of blocks, the function should return 0.

For example, given:

A[0] = 1
A[1] = 2
A[2] = 3
A[3] = 4
A[4] = 3
A[5] = 4
A[6] = 1
A[7] = 2
A[8] = 3
A[9] = 4
A[10] = 6
A[11] = 2

the function should return 3, as explained above.

Write an efficient algorithm for the following assumptions:

N is an integer within the range [1..100,000];
each element of array A is an integer within the range [0..1,000,000,000].

비어 있지 않은 정수 배열 A가 주어집니다. 이 배열은 N개의 정수로 구성되어 있습니다.

피크(peak)는 이웃한 요소들보다 큰 배열 요소입니다. 더 정확히 말하면, 피크는 0 < P < N − 1이고 A[P − 1] < A[P] > A[P + 1]인 인덱스 P입니다.

예를 들어, 다음과 같은 배열 A가 있습니다:

A[0] = 1
A[1] = 2
A[2] = 3
A[3] = 4
A[4] = 3
A[5] = 4
A[6] = 1
A[7] = 2
A[8] = 3
A[9] = 4
A[10] = 6
A[11] = 2

이 배열에는 정확히 세 개의 피크가 있습니다: 3, 5, 10.

이 배열을 동일한 수의 요소를 포함하는 블록으로 나누고자 합니다. 더 정확히 말하면, 다음과 같은 블록을 생성할 수 있는 숫자 K를 선택하고자 합니다:

A[0], A[1], …, A[K − 1], A[K], A[K + 1], …, A[2K − 1], … A[N − K], A[N − K + 1], …, A[N − 1].

또한, 각 블록에는 적어도 하나의 피크가 포함되어야 합니다. 블록의 극단 요소(예: A[K − 1] 또는 A[K])도 피크가 될 수 있지만, 이 경우 이웃 요소(인접 블록에 있는 요소 포함)가 있어야 합니다.

목표는 배열 A를 최대한 많은 블록으로 나누는 것입니다.

배열 A는 다음과 같이 블록으로 나눌 수 있습니다:

한 블록 (1, 2, 3, 4, 3, 4, 1, 2, 3, 4, 6, 2). 이 블록에는 세 개의 피크가 포함되어 있습니다.
두 블록 (1, 2, 3, 4, 3, 4) 및 (1, 2, 3, 4, 6, 2). 각 블록에는 피크가 하나씩 포함되어 있습니다.
세 블록 (1, 2, 3, 4), (3, 4, 1, 2), (3, 4, 6, 2). 각 블록에는 피크가 하나씩 포함되어 있습니다. 특히 첫 번째 블록 (1, 2, 3, 4)에는 A[3]에 피크가 있습니다. 이는 A[2] < A[3] > A[4]이기 때문입니다. 비록 A[4]는 인접 블록에 있습니다.
그러나 배열 A는 네 블록 (1, 2, 3), (4, 3, 4), (1, 2, 3) 및 (4, 6, 2)으로 나눌 수 없습니다. 왜냐하면 (1, 2, 3) 블록에는 피크가 포함되어 있지 않기 때문입니다. 특히 (4, 3, 4) 블록에는 두 개의 피크 A[3] 및 A[5]가 포함되어 있습니다.

배열 A를 최대한 많은 블록으로 나눌 수 있는 최대 수는 세 개입니다.

다음 함수를 작성하세요:

class Solution { 
    public int solution(int[] A); 
}

이 함수는 비어 있지 않은 정수 배열 A가 주어졌을 때, 배열 A를 나눌 수 있는 최대 블록 수를 반환해야 합니다.

배열 A를 일부 블록으로 나눌 수 없는 경우, 함수는 0을 반환해야 합니다.

예를 들어, 다음과 같은 배열 A가 주어졌을 때:

A[0] = 1
A[1] = 2
A[2] = 3
A[3] = 4
A[4] = 3
A[5] = 4
A[6] = 1
A[7] = 2
A[8] = 3
A[9] = 4
A[10] = 6
A[11] = 2

함수는 위에서 설명한 대로 3을 반환해야 합니다.

다음 가정을 위한 효율적인 알고리즘을 작성하세요:

N은 [1…100,000] 범위 내의 정수입니다.
배열 A의 각 요소는 [0…1,000,000,000] 범위 내의 정수입니다.

문제풀이

import java.util.*;

class Solution {
    public int solution(int[] A) {
        int N = A.length;
        if (N < 3) return 0;

        List<Integer> peaks = new ArrayList<>();
        for (int i = 1; i < N - 1; i++) {
            if (A[i] > A[i-1] && A[i] > A[i+1]) {
                peaks.add(i);
            }
        }
        if (peaks.size() == 0) return 0;

        for (int size = 1; size <= N; size++) {
            if (N % size != 0) continue;
            int blockCount = N / size;
            boolean[] blockHasPeak = new boolean[blockCount];
            int peakIndex = 0;

            for (int peak : peaks) {
                int blockIndex = peak / size;
                blockHasPeak[blockIndex] = true;
            }

            boolean allBlocksHavePeak = true;
            for (boolean hasPeak : blockHasPeak) {
                if (!hasPeak) {
                    allBlocksHavePeak = false;
                    break;
                }
            }

            if (allBlocksHavePeak) {
                return blockCount;
            }
        }

        return 0;
    }
}

제출결과

문제풀어보기 -> https://app.codility.com/programmers/lessons/10-prime_and_composite_numbers/peaks/