230206 codility SparseBinaryDecomposition(자바스크립트 시간초과)

매일 매일 하루 한 문제씩.
꾸준히 이어가는 코딩테스트 풀이 기록 ✅

오늘 문제는 풀어낸 것 같으면서도 시간초과로 인해 퍼포먼스 테스트는 통과하지 않은.
이 부분이 문제일 것 같다고 추측되는 부분은 있는데 정확하진 않아서... 좀 찜찜.

시간 초과 부분은 결국 효율성과 직결되는 부분이기에 강의 보면서 좀 더 공부를 해야겠다.
BigO ... 흠. 어쨌든!! 해보자.

---

문제 링크

SparseBinaryDecomposition

---

Javascript

시간 초과가 나지 않았으면 하는 마음으로 나름대로의 가드클로즈를 만들어보았는데 제대로 적용되지 않는 로직인 것 같다.

지금 제일 의심스러운 부분은 validator function에서 .split('11') 이부분. 11을 포함한 것으로 split을 하려면 결국 모든 string을 다 뒤져봐야 하기 때문에 여기에서 효율성 문제가 발생하는게 아닌가 싶다.

딱히 좋은 방법이 떠오르지 않는 상황에서 시간이 많이 흘렀기에 오늘은 여기까지 내용을 바탕으로 TIL을 작성한다.

내가 푼 내용(시간 초과. performance 부분 취약)

// you can write to stdout for debugging purposes, e.g.
// console.log('this is a debug message');

function validator(number) {
  const array = number.split('11');
  return array[1] === undefined;
}

function solution(N) {
  // Implement your solution here
  for (let i = 0; i < N / 2 + 1; i += 1) {
    const binaryNumber1 = i.toString(2);
    const binaryNumber2 = (N - i).toString(2);

    const isSparseOf1 = validator(binaryNumber1);

    if (isSparseOf1) {
      const isSparseOf2 = validator(binaryNumber2);
      if (isSparseOf2) {
        return i;
      }
    }
  }

  return -1;
}

---

급한 마음에 풀다보니 변수명이 영... 구리긴 하다.
그렇다고 단순하게 P, Q 하기도 참 그렇고. 이럴 땐 어떻게 해야할까 고민스럽다.

지난번 코테 면접에서 변수명에 대한 부분도 지적을 받았기에.

생각해보면 쓰리지만 다시 생각해볼점이 많았던 면접 같다.

잘 해보자.

---

간단한 단어 정리
sparse: 밀도가 적은, 흩어져 있는
decomposition: 분해, 부패