Codility Lesson10 - Peaks

🔍문제

---

 

Peaks coding task - Learn to Code - Codility

어떤 배열을 블럭으로 나눴을 때, 모든 블럭이 peak인 숫자를 가지고 있어야한다. 이 때, 가능한 최대 블럭의 개수를 구하면 된다.

 

✏️ 풀이 - JS

---

아래처럼 풀면 보나마나 performance에서 timeout error가 뜰 것 같았지만 한 번 submit해보았다.

정확도 test는 다 맞았지만 시간복잡도 O(N**2)로 역시나 timeout error가 발생했다.

function solution(A) {
    const N = A.length;
    if(N < 3) return 0;

    let peaks = [];

    for(let i = 1; i < N-1; i++) {
        if(A[i] > A [i-1] && A[i] > A[i+1]) peaks.push(i);
    }

    if(peaks.length === 0) return 0; //peak인 숫자가 없는 경우


    let maxBlockCnt = 1;

   for(let i = 2; i <= peaks.length; i++) { //블럭의 최대 개수는 peak의 수 이하이다.
        if(N % i === 0) {
            const K = N / i; // 블럭 안의 원소 개수
            let ifValid = true; // 유효한 블럭 개수인지 check

            for(let j = 0; j < i; j++) {
                const start = j*K;
                const end = (j+1)*K;
                let idx = 0;
                let ifBlockHasPeak= false; //해당 블럭이 peak을 가지고 있는지

                while(idx < peaks.length) {
                    if(peaks[idx] >= start && peaks[idx] < end) {
                        ifBlockHasPeak = true;
                        break;
                    } else {
                        idx++;
                    }
                }

                if(ifBlockHasPeak) {
                    continue;
                } else {
                    ifValid = false;
                    break;
                }
            }

            if(!ifValid) continue;
            maxBlockCnt = i;
        }
   }

   return maxBlockCnt;
}

따라서 가운데 while문을 없애기 위해, 부분 블럭이 peak을 가지고 있는지 체크하는 것이 아니라 peaks 배열을 순회하면서 peak을 블럭에 배분하는 식으로 만들었다. peak을 최종으로 배분하고나서 i가 idx와 같으면 가능한 블럭의 수로 보고 return하였다.
가능한 블럭의 수 중에 가장 '큰'블럭의 수 이므로 가능한 가장 큰 블럭의 수는 peak의 개수와 동일하기 때문에(모든 블럭에 peak이 하나씩 들어있다는 가정) 뒤에서부터 배분하도록 하였다.

시간복잡도는 O(N * log(log(N)))로 total 100%가 나왔다.

function solution(A) {
    const N = A.length;
    if(N < 3) return 0;

    let peaks = [];

    for(let i = 1; i < N-1; i++) {
        if(A[i] > A [i-1] && A[i] > A[i+1]) peaks.push(i);
    }

    const peakN = peaks.length;
    if(peakN === 0) return 0; //peak인 숫자가 없는 경우


   for(let i = peakN; i >= 2; i--) { //블럭의 최대 개수는 peak의 개수 이하이다.
        if(N % i === 0) {
            const K = N / i; // 블럭 안의 원소 개수

            let idx = 0; //peak이 배치된 블럭의 수  

            for(let i in peaks) { //peak을 블럭에 배치한다.
                let start = idx*K;
                let end = (idx+1)*K;
                if(peaks[i] >= start && peaks[i] < end) {
                    idx++;    
                }
            }

            if(idx === i) return i;
        }
   }

   return 1;
}