Lesson 10. Prime and composite numbers - Peaks #1

1. 문제

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:
  int solution(vector<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].

 

주어진 배열을 나눌 때,  최대 블럭 개수를 구하는 문제.

 

블럭 조건

• 동일한 크기로 나누어야 한다
• 각 블럭에는 Peak가 반드시 1개이상 포함되어야 한다 (Peak: A[P - 1] < A[P] > A[P + 1])

예시)

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

Peak: A[3], A[5], A[10]

블럭 1개(가능): (1, 2, 3, 4, 3, 4, 1, 2, 3, 4, 6, 2)

블럭 2개(가능): (1, 2 ,3, 4, 3, 4), (1, 2, 3, 4, 6, 2)

블럭 3개(가능): (1, 2, 3, 4), (3, 4, 1, 2), (3, 4, 6, 2)

블럭 4개(불가능): (1, 2, 3), (4, 3, 4), (1, 2, 3), (4, 6, 2)

 

블럭을 4개로 나눌 경우, Peak가 포함되지 않는 블럭이 있음을 알 수 있다.

 

2. 매개변수 조건

• Vector A 크기(N): 1 ~ 100,000
• Vector A 값 범위: 0 ~ 1,000,000,000

 

3. 문제풀이 전략

'N을 동일한 크기로 나눈다'가 문제 해결 실마리이다.

N을 동일한 크기로 나누려면 어떻게 해야할까? 하나의 블럭에는 몇 개의 요소를 포함해야 할까?

이 모든 물음의 대답은 '약수'이다.

N을 N의 약수로 나누면, 같은 크기의 블럭으로 나눌 수 있다.

따라서 약수로 나누었을 때, 몫이 블럭수가 된다.

 

 

4. 예제 분석

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

Peak: A[3], A[5], A[10]

약수	블럭	결과
12	1	(1, 2, 3, 4, 3, 4, 1, 2, 3, 4, 6, 2)
6	2	(1, 2 ,3, 4, 3, 4), (1, 2, 3, 4, 6, 2)
4	3	(1, 2, 3, 4), (3, 4, 1, 2), (3, 4, 6, 2)
3	4	(1, 2, 3), (4, 3, 4), (1, 2, 3), (4, 6, 2)
2	6	(1, 2), (3, 4), (3, 4), (1, 2),  (3, 4), (6, 2)
1	12	(1), (2), (3), (4), (3), (4), (1), (2), (3), (4), (6), (2)

 

위 결과를 보면, 가장 작은 약수로 나누었을 때, 최대 블럭수가 나온다.

가장 작은 약수로 나누고, 나눠진 블럭에 peak 값이 있는지 확인하는 작업을 하면 답을 도출할 수 있다.

 

5. 코드 (C++)

peak 구하기 → 약수 구하기 → 약수 정렬 → 최대 블럭 수 구하기

#include <cmath>
#include <algorithm>

int solution(vector<int> &A) {

    //peak 구하기
    vector<int> peaks = {};
    for(size_t i = 1; i < A.size()- 1; i++)
    {
        if(A[i - 1] < A[i] && A[i] > A[i + 1])
        {
            peaks.emplace_back(i);
        }
    }

    //peak가 없으면, block도 없다
    if(peaks.empty()) return 0;

    //약수 구하기
    int divisor = 1;
    int N = static_cast<int>(A.size());
    vector<int> factors = {};
    while(divisor < sqrt(N))
    {
        if(N % divisor == 0)
        {
            factors.emplace_back(divisor);
            factors.emplace_back(N / divisor);
        }
        divisor++;
    }
    if(divisor * divisor == A.size()) factors.emplace_back(divisor);
    
    //약수 정렬
    sort(factors.begin(), factors.end());

    //최대 블럭 수 구하기
    //가장 작은 약수 1과, 가장 큰 약수 N은 건너뛴다
    for(size_t i = 1; i < factors.size() - 1; i++)
    {
        bool max_block = true; //최대 블럭 수를 구했는지 확인하는 변수
        int start = 0; //블럭 시작 index
        int end = factors[i] - 1; //블럭 끝 index
        do
        {
            //블럭 안에 peak가 있는지 확인
            bool peak_exists = false;
            for(size_t p = 0; p < peaks.size(); p++)
            {
                if(start <= peaks[p] && peaks[p] <= end) //peak가 있다
                {
                    peak_exists = true;
                    break;
                }
            }

            if(!peak_exists) //블럭 안에 peak가 없다면
            {
                max_block = false; //최대 블럭 조건이 성립하지 않는다
                break;
            }

            start += factors[i];
            end += factors[i];
        }while(start < N);

        if(max_block) return N / factors[i];
    }

    //여기까지 최대 블럭 수를 못찾았다면, 블럭은 1개일수밖에 없다
    return 1;
}

 

 

6. 결과