Lesson 10. Prime and composite numbers - Peaks #3 (속도 개선-2)

이미 Peaks #2에서 100%를 달성했지만, 조금 더 수정해보자.

 

1. 속도 개선 아이디어

Peak 조건을 제외하고, 최대 블럭 수를 구한다면, 최대 블럭 수는 몇 개 일까? 정답, N개

그렇다면 Peak 조건을 추가해서, 최대  블럭수를 구한다면, 최대 블럭 수는 몇 개 일까? Peak개

 

이전까지는 최소 약수로 시작해서, 최대 블럭 수를 찾아봤다.

이번에는 반대로 최대 블럭 수(Peak 개)로 시작해서, 최소 블럭 수(1개) 순서로 찾아보면 어떨까? 

이렇게 하면, 중간에 '약수를 구하는 코드'와 '약수 정렬 코드'를 제거할 수 있다.

 

2. 코드 (C++)

peak 구하기 → 최대 블럭 수 구하기

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 N = static_cast<int>(A.size());
    int max_block = static_cast<int>(peaks.size());
    while(max_block > 1)
    {
        //약수 확인 
        if(N % max_block == 0) //max_block이 약수라면
        {
            int divisor = N / max_block; //각 블럭의 요소 개수
            int start = 0; //블럭 시작 index
            int end = divisor - 1; //블럭 끝 index
            size_t p = 0;
            do
            {
                //블럭 안에 peak가 있는지 확인
                while(p < peaks.size())
                {
                    if(start <= peaks[p] && peaks[p] <= end) break;
                    p++;
                }

                if(p >= peaks.size()) break;

                start += divisor;
                end += divisor;
            }while(start < N);

            if(start >= N) return N / divisor; //최대 블럭 수를 찾았다
        }
        max_block--;
    }

    return max_block;
}

 

 

3. 결과