기능개발

네?... 무슨 말이죠 이게?

이제야 이해가 되네요...

1. speeds의 원소의 크기만큼 progresses의 원소의 크기가 증가한다.
2. progresses의 0번 원소가 100이 됐을 때 1번 원소도 100이라면 같이 내보난다... 2도.. 3도...
3. 다시 sppeds의 원소 크기만큼 증가시키고 남아있는 원소중 가장 빠른 인덱스의 크기가 100이되면 2.와 같은 과정을 반복한다

나의 풀이

function sol00(progresses, speeds) {
  let answer = [];
  let pLength = progresses.length;

  while (pLength > 0) {
    for (let i = 0; i < pLength; i++) {
      if (progresses[i] < 100) {
        progresses[i] += speeds[i];
      }
    }

    if (progresses[0] >= 100) {
      let index = 0;
      while (pLength > 0 && progresses[0] >= 100) {
        progresses.shift();
        speeds.shift();
        pLength--;
        index++;
      }

      answer.push(index);
    }
  }

  return answer;
}

생각보다 쉽게 작성됐다
반복문의 중첩으로 시간복잡도 자체는 높아보이지만 계속해서 양이 줄어들기 때문에 실제 작동시간은 오래걸리지 않을 것이다

시간복잡도 : $O(n^2)$

다른 사람의 풀이

function sol10(progresses, speeds) {
  let answer = [0];
  let days = progresses.map((progress, index) =>
    Math.ceil((100 - progress) / speeds[index])
  );
  let maxDay = days[0];

  for (let i = 0, j = 0; i < days.length; i++) {
    if (days[i] <= maxDay) {
      answer[j] += 1;
    } else {
      maxDay = days[i];
      answer[++j] = 1;
    }
  }

  return answer;
}

수학적으로 풀었다. 중학생때 달팽이가 우물을 오르는 문제를 풀었던게 기억난다. 물론 그것과는 예외처리가 다르지만...

개인적인 경험으로 수학적으로 접근해서 푼 것들이 효율이 매우 좋았기 때문에 이것도 그렇다고 생각한다

시간복잡도 : $O(n)$

속도 비교

이상한데?

뭐지 이상한데?... 원소의 크기를 10배 늘렸는데 속도가 줄어들리가 없다.
이해가 안간다

2024 06 20 추가

혹시나 내가 코드를 잘못짜서 원본 배열이 삭제됐나 싶어서 실행순서를 반대로 바꿨다. 거기에 배열도 더 길게 생성해봤다.
오히려 차이가 더 커졌다

배열도 정상적으로 커지고 있는 모습이다. 일이 10배, 진행 속도도 10배면 진행 시간은 당연히 같아야하는데 이유를 모르겠다
오히려 숫자가커서 (의미가 없을 정도로 아주아주아주아주)미세하게 느려져야하는게 아닌가?

그럼 그렇지

10배로 올렸으면 조건도 10배로 올려야했다

휴... 드디어 결과다운 결과가 나왔다

배운 점

1. 수학적으로 푸는 방법은 항상 좋은 결과를 가져온다

2. 부하를 늘릴때 기존 코드와 호환이 되는지 잘 생각하고 짜자

전체 코드

// const progresses = [95, 90, 99, 99, 80, 99];
// const speeds = [1, 1, 1, 1, 1, 1];

const progresses = [
  83, 14, 99, 71, 69, 7, 4, 78, 15, 42, 77, 5, 27, 66, 55, 69, 83, 76, 10, 91,
  3, 49, 12, 80, 25, 100, 87, 30, 5, 59,
];

const speeds = [
  2, 8, 4, 6, 1, 4, 2, 10, 7, 9, 5, 4, 8, 2, 9, 3, 7, 4, 3, 8, 1, 4, 1, 7, 9, 5,
  1, 3, 4, 6,
];

function long(progresses, speeds, n1) {
  let progresses2 = [];
  let speeds2 = [];

  for (let i = 0; i < n1; i++) {
    progresses2 = progresses2.concat(progresses);
    speeds2 = speeds2.concat(speeds);
  }

  return { progresses2, speeds2 };
}

function big(progresses, speeds, n2) {
  const progresses3 = progresses.map((progress) => progress * n2);
  const speeds3 = speeds.map((speed) => speed * n2);

  return { progresses3, speeds3 };
}

const n1 = 10;
const n2 = 10;

const longResult = long(progresses, speeds, n1);
const bigResult = big(progresses, speeds, n2);

function sol00(progresses, speeds) {
  let answer = [];
  let pLength = progresses.length;

  while (pLength > 0) {
    for (let i = 0; i < pLength; i++) {
      if (progresses[i] < 100) {
        progresses[i] += speeds[i];
      }
    }

    if (progresses[0] >= 100) {
      let index = 0;
      while (pLength > 0 && progresses[0] >= 100) {
        progresses.shift();
        speeds.shift();
        pLength--;
        index++;
      }

      answer.push(index);
    }
  }

  return answer;
}

function sol01(progresses, speeds) {
  let answer = [];
  let pLength = progresses.length;

  while (pLength > 0) {
    for (let i = 0; i < pLength; i++) {
      if (progresses[i] < 1000) {
        progresses[i] += speeds[i];
      }
    }

    if (progresses[0] >= 1000) {
      let index = 0;
      while (pLength > 0 && progresses[0] >= 1000) {
        progresses.shift();
        speeds.shift();
        pLength--;
        index++;
      }

      answer.push(index);
    }
  }

  return answer;
}

function sol10(progresses, speeds) {
  let answer = [0];
  let days = progresses.map((progress, index) =>
    Math.ceil((100 - progress) / speeds[index])
  );
  let maxDay = days[0];

  for (let i = 0, j = 0; i < days.length; i++) {
    if (days[i] <= maxDay) {
      answer[j] += 1;
    } else {
      maxDay = days[i];
      answer[++j] = 1;
    }
  }

  return answer;
}

function sol11(progresses, speeds) {
  let answer = [0];
  let days = progresses.map((progress, index) =>
    Math.ceil((1000 - progress) / speeds[index])
  );
  let maxDay = days[0];

  for (let i = 0, j = 0; i < days.length; i++) {
    if (days[i] <= maxDay) {
      answer[j] += 1;
    } else {
      maxDay = days[i];
      answer[++j] = 1;
    }
  }

  return answer;
}

function runtime(func, progresses, speeds) {
  const n = 100000;
  const startTime = Date.now();

  for (let i = 0; i < n; i++) {
    const progressesCopy = [...progresses];
    const speedsCopy = [...speeds];
    func(progressesCopy, speedsCopy);
  }

  const endTime = Date.now();
  const executionTime = endTime - startTime;

  console.log(
    `${func.name} 함수 반복 횟수 ${n}회, 실행시간 : ${executionTime} ms`
  );
}

const list = [sol00, sol10, sol01, sol11];

for (let i = 0; i < 2; i++) {
  for (let k = 0; k < 3; k++) {
    runtime(list[i], progresses, speeds);
  }
  console.log(`개발할 것들이 ${n1}배로 많아진 경우`);
  for (let k = 0; k < 3; k++) {
    runtime(list[i], longResult.progresses2, longResult.speeds2);
  }
  console.log(`개발양과 속도가 ${n2}배로 커진 경우`);
  for (let k = 0; k < 3; k++) {
    runtime(list[i + 2], bigResult.progresses3, bigResult.speeds3);
  }
  console.log("---");
}