[codility] JS Lv4-1 ForgRiverOne

📌 4-1 ForgRiverOne

 

내풀이 1 (72%) 시간초과

function solution(X, A) {
  ans = -1;
  let idxArr = new Array(X).fill(0);

  const isContinue = (arr) => {
    const idx = arr.findIndex((ele) => ele === 0);
    if (idx >= 0) return false;
    else return true;
  };

  for (let i = 0; i <= A.length; i++) {
    idxArr[A[i] - 1] = 1;
    if (isContinue(idxArr)) {
      ans = i;
      break;
    }
  }

  return ans;
}

1) X크기의 0으로 채워진 빈 배열 생성

2) A 배열을 돌며 해당 idx-1 (0부터 시작하므로) 를 채움

3) 채울때마다 해당 배열이 연속되었는지 확인 (isContinue)

 

 

내 풀이 2( 82%) 시간 초과

function solution(X, A) {
  ans = -1;
  let idxArr = new Array(X).fill(0);

  const isContinue = (arr) => {
    let ans = true
    for (let i = 0; i < arr.length; i++) {
      if (arr[i] === 0) {
          ans = false
          break
      }
    }
    return ans
  };

  for (let i = 0; i <= A.length; i++) {
    idxArr[A[i] - 1] = 1;
    if (isContinue(idxArr)) {
      ans = i;
      break;
    }
  }

  return ans;
}

isContinue 부분을 인덱스가 0인걸 찾으면 바로 break 하도록 변경했지만

시간초과 테케는 2개를 통과하지 못했다.

 

 

다른 풀이 (100%)

function solution(X, A) {
    idxArr = new Array(A.length).fill(0)
    idxSum = 0
    for (let i=0; i<A.length ; i++){
        if (idxArr[A[i]-1] === 0){
            idxArr[A[i]-1] =1
            idxSum +=1
        }
        if (idxSum === X) return i
    }
    return -1
}

1 )A를 돌면서 idxArr의 인덱스 A 값이 0이면  1로 채우고 합산을하다.

2) 합산이 X와 같아지면 X만큼의 배열이 다 채워진것이므로 그때의 i (초)를 return

 

 

🥳  오늘 배운 점

시간을 감소시키기 위해서는 기존의 방법을 줄이는 것이 아니라 새로울 아이디어가 필요하다 .