CountingElements.FrogRiverOne 문제 도와주세요.

eyabc commented 4 years ago

https://app.codility.com/programmers/lessons/4-counting_elements/frog_river_one/

마지막 2개에 timeout 이 뜹니다.

function solution2 (X, A) {
  let time = -1;
  let location = 0;
  if (A.length < X) return -1;

  while (location < X) {
    const newLocation = A.indexOf(++location);
    if (newLocation === -1) return -1;
    else if (newLocation > time) {
      time = newLocation;
    }
  }
  return time;
}

나는 이렇게 풀었어 문제 해결해서 알려줘!!!! (이렇게 물어보면 안됩니다 ㅎㅎ)

내 코드에 대한 설명 . 어려운 점 구체적으로 !!

JunilHwang commented 4 years ago

[풀이완료] https://github.com/DKU-STUDY/Algorithm/tree/master/codility_training/lesson.04.CountingElements.FrogRiverOne

[원인]

function solution2 (X, A) {
  let time = -1;
  let location = 0;
  if (A.length < X) return -1;

  while (location < X){  // 시간복잡도 : O(n)
    const newLocation = A.indexOf(++location);  // 시간복잡도 : O(m)
    if (newLocation === -1) return -1;
    else if (newLocation > time) {
      time = newLocation;
    }
  }

  // 최종 시간복잡도 : O(n * m)
  // 문제 해결을 위해선 O(n) 으로 줄여야 함
  return time;
}

현재 시간 복잡도가 O(n * m) 인 상태

[ 해결방법 ]

이를 해결하기 위해선 js의 Set 이라는 것을 사용하면 됨!

일단 현재 코드에서의 문제는 각 반복문마다 중복체크를 하는데, 이것 때문에 시간복잡도가 매우 커짐 그래서 탐색에 대한 자료구조를 사용하면 되는데, js는 Set이 이에 적합하다고 볼 수 있음!

Set은 기본적으로 집합에 대한 개념이기 때문에 중복된 자료를 저장할 수 없는 형태이므로 다음과 같이 코드를 짤 수 있는데

function solution(X, A) {
  const set = new Set()
  const len = A.length
  for (let i = 0; i < len; i++) { // O(n)
    set.add(A[i])
    if (set.size === X) return i
  }
  return -1
}

이럴 경우 O(n) 으로 해결 가능!

eyabc commented 4 years ago

감사감사 선배님짱!~!

DKU-STUDY / Algorithm

CountingElements.FrogRiverOne 문제 도와주세요. #1