Codility Lesson10 - Flags

🔍 문제

---

 

이전 풀었던 peaks 문제와 비슷한데, 조금 더 꼬아서 낸 것 같다. 먼저 주어진 배열 A에서 peak을 구한다. 각 peak에는 깃발을 꽂을 수 있는데, peak에 깃발을 꽂을 수 있는 조건은 다음과 같다.

1. peak P와 Q사이의 거리(배열 A에서 index)가 챙겨간 깃발의 갯수보다 크거나 같아야 깃발을 꽂을 수 있다.

2. 이 때, 배열 A의 peak에 꽂을 수 있는 가장 큰 깃발의 수를 구하면 된다.

 

Flags coding task - Learn to Code - Codility

 

✏️ 풀이 - JS

---

정확도는 다 맞았는데 performance에서 28%가 나왔다. timeout error가 나지 않게 발버둥 쳐봤지만 도저히 아무리 생각해도 모르겠어서 구글의 도움을 받았다. 아래는 맨 처음 raw하게 작성한 코드이다.

function solution(A) {
  const N = A.length;
  if (N < 3) return 0; // 배열 A의 크기가 3이하인 경우

  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 < 2) return peaks.length;

  let maxSetFlags = 0;

  for (let k = peaks.length; k >= 2; k--) {
    //가능한 가장 큰 k(챙겨갈 깃발개수)는 peak개수랑 같다.
    if (k <= maxSetFlags) return maxSetFlags; // k 가 maxSetFlags 보다 작은 경우 더 이상 계산할 필요X

    let current = 0;
    let flags = 0;

    for (let i = 1; i < peaks.length; i++) {
      //조건에 맞는 peak을 확인 한 후 flag를 꽂아준다.
      if (flags === k - 1) break;

      if (Math.abs(peaks[i] - peaks[current]) >= k) {
        flags++;
        current = i;
      }
    }

    if (flags > 0) {
      flags += 1;
      if (flags > maxSetFlags) maxSetFlags = flags;
    }
  }

  return maxSetFlags;
}

다음은 두번째로 작성한 코드이다.

function solution(A) {
  if (A.length <= 2) return 0;

  let peaks = [];

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

  let size = peaks.length;

  if (size <= 2) return size;

  let maxFlag = parseInt(Math.sqrt(peaks[size - 1] - peaks[0]) + 1);

  for (let i = maxFlag; i >= 2; --i) {
    let count = 1;
    let curPos = peaks[0];
    for (let j = 1; j < size; ++j) {
      if (curPos + i <= peaks[j]) {
        curPos = peaks[j];
        ++count;
      }
    }
    if (count >= i) return i;
  }

  return 2;
}

위의 코드와 로직은 똑같다. 대체로 더 깔끔해진 것을 제외하고 가장 중요한 부분은 바로 이 부분이다.
이전의 코드에서는 k가 될 수 있는 가장 큰 수를 peak의 개수로 보았다.

for(let k = peaks.length; k >= 2; k--)

하지만 아래의 코드에서는 다음과 같이 최대 깃발의 수를 제한한다.

let maxFlag = parseInt(Math.sqrt(peaks[size-1] - peaks[0]) + 1);

이 공식을 통해서 불필요한 계산을 단축시킴으로써 performance test를 모두 통과할 수 있었다. 문제는 대체 왜?!?! 인지 잘 모르겠다는 것이다. 내 개념으로는 모든 peak에 깃발을 꽂을 수 있다고 생각했을 때 가능한 최대 깃발의 수를 peak의 개수로 생각했었다. 하지만 이렇게하면 불필요한 계산이 많이 따라서 performance test를 모두 통과하지 못하는 것으로 보인다.

저 공식에 따르면 최대 가능한 깃발 수는 맨 뒤에있는 peak과 맨 앞에 있는 peak의 거리차의 제곱근 + 1을 정수로 표현한 값이다.
이 문제만 지금 세시간째 보고있는데 일단 나중에 다시 생각해봐야겠다. 뇌정지왔다...

아무도 찾아오지 않는 산골짜기 블로그에 누군가가 이 글을 읽고 알려줄 확률은 얼마나 될까...?

혹여 누군가 이곳을 지나가시다가 답을 알고계신다면 댓글 부탁드립니다...(_ _)