[Codility] Lesson10. Prime And Composite Numbers-Flags C언어 풀이

#define MAX_SIZE 200000
int peak[MAX_SIZE], top = -1;

int solution(int A[], int N) {
    //N의 길이가 1 ~ 400,000 이므로 3개이하의 배열에서는 peak가 생성되지 않는다.
    if(N < 3)
        return 0;
    
    for(int i = 1; i < N-1; i++){
        if(A[i-1] < A[i] && A[i+1] < A[i])
            peak[++top] = i;
    }
    //N의 길이가 peak가 0 or 1인 경우 아래 반복문은 실행되지 않는다. 바로 정답 출력 
    int answer = top+1;
    
    for(int i = 1; i <= top; i++){
        /*
        flag : 사용 할 깃발 수
        used : 사용 한 깃발 수
        index1,2 : 앞뒤 peak의 길이를 체크
        */

        int flag = i+1, used = 1, index1 = 0, index2 = 1;
        while(index2 <= top){
            if(peak[index2] - peak[index1] >= flag){
                index1 = index2;
                //깃발을 다 사용하면 빠져나옴
                if(++used == flag){
                    answer = flag;
                    break;
                }
            }
            index2++; 
        }
        //깃발을 다 사용하지 못하였으므로 종료
        if(used != flag){
            break;
        }
    }
    
    return answer;
}