[Codility][Prime/Composite] Peaks & Flags

minnsane·2020년 9월 17일
0

Algorithms

목록 보기
6/8

Peaks

문제

https://app.codility.com/programmers/lessons/10-prime_and_composite_numbers/peaks/start/

분석

이건 너무 모르겠어서 구글링 힘을 많이 받아따...

코드

const solution = A => {
  let len = A.length;
  let peaks = [];

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


  for(let i=peaks.length; i>=1; i--){
    if(len%i===0){
      let numMember = len/i;
      let index = 0;
      for(let peak of peaks){
        let start = index*numMember;
        let end = (index+1)*numMember;
        if(peak>=start && peak<end){
          index++;
        }
      }
      if(index===i) return i;
    }
  }
  
}
  • 그룹의 수는 peak의 갯수보다 커질 수 없다!
  • peak이 제대로 분배되었느냐를 체크할 때 왜 나는 배열을 떠올렸을까.... 인덱스를 높여가면서 그 위치에 있는지 없는지만 체크하는것이 훨씬 좋은 방법이다!

Flags

코드

정확도 100% 퍼포먼스 0%

const solution = A => {
  let len = A.length;
  let peaks =[];

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

  for(let i=peaks.length; i>=1; i--){
    let flags = i;
    let position = 0;

    while(flags > 0 && position < len){
      if(peaks.includes(position)){
        flags--;
        position += i;
      }else{
        position++;
      }
    }

    if(flags===0) return i;
  }
  
}

Codility 솔루션의 도움을 받아 작성한 코드

const solution = A => {
  let len = A.length;
  let nextPeak = new Array(len).fill(-1);
  let peaksNum = 0;

  for(let i=len-2; i>=0; i--){
    if(A[i]>A[i-1] && A[i]> A[i+1]){
      nextPeak[i] = i;
      peaksNum++;
    }else{
      nextPeak[i] = nextPeak[i+1];
    }
  }
  if(peaksNum===0) return 0;

  for(let i=peaksNum; i>=1; i--){
    let flags = i;
    let pos = 0;
    while(flags>0 && pos<len){
      pos = nextPeak[pos];
      if(pos === -1) break;
      flags--;
      pos += i;
    }
    if(flags===0) return i;
  }
}
  • 해당 지점에서 가장 가까운 다음 peak을 찾아서 깃발을 꽂는게 핵심!
  • 이런건 도대체 어떻게 생각하는걸까...
profile
Knope's not-so-secret binder

0개의 댓글