프로그래머스 LEVEL 2(우박수열 정적분)

사용 언어 : javascript
해결 날짜 : 2022-12-07
해결 방법 :
- 우박수열을 구하는 동안, widths에 누적된 넓이를 push()
- 누적된 넓이를 구한 다음, 인자로 받은 ranges를 돌며
  - 넓이를 구할 수 없을 경우(x2 < x1) answer에 -1.0 push()
  - 그 외의 경우 answer에 x2까지의 넓이 - x1까지의 넓이 push()
회고 :
- 처음에 y 좌표 값들을 따로 구하고, 그 좌표 값들에 대한 각각의 넓이를 구한 뒤, slice()를 사용해 문제를 해결했다.
  - 통과하긴 했지만, 코드가 비효율적인 것 같아 y 좌표 값들을 따로 구하고 각 넓이를 구하는 대신 한번에 넓이를 구하는 방식으로 변경했다.
- 그 다음 누적된 넓이가 아닌 각 구간에 대한 넓이를 저장하다보니, 나중에 구간이 많아질 경우 slice()를 사용하는게 비효율적이라고 생각되었다.
  - 따라서 각 구간에 대한 각각의 넓이가 아닌, 현재까지의 누적된 넓이를 저장하고 x2까지의 넓이에서 x1까지의 넓이를 빼는 방식으로 변경했다.
  - 이를 통해 O(ranges * widths)가 아닌 O(ranges * 1)의 시간 복잡도로 각 범위에 대한 넓이를 구할 수 있었다.

코드

function solution(k, ranges) {
  const answer = [];
  const widths = [0];
  let prevY = k,
    currentY = k;

  while (currentY > 1) {
    if (currentY % 2 === 0) currentY /= 2;
    else currentY = currentY * 3 + 1;

    const width = (prevY + currentY) / 2;
    prevY = currentY;

    widths.push(widths[widths.length - 1] + width);
  }

  for (const range of ranges) {
    const x1 = range[0],
      x2 = widths.length + range[1] - 1;

    if (x2 - x1 < 0) answer.push(-1.0);
    else answer.push(widths[x2] - widths[x1]);
  }

  return answer;
}

출처: 프로그래머스 코딩 테스트 연습, https://school.programmers.co.kr/learn/challenges