Programmers / Level 2 / 우박수열 정적분 / JS

문제 간단설명

우박수열은 1을 만들기 위해 다음과 같은 단계를 거칩니다.

1-1. 입력된 수가 짝수라면 2로 나눕니다.
1-2. 입력된 수가 홀수라면 3을 곱하고 1을 더합니다.
2. 결과로 나온 수가 1보다 크다면 위 작업을 반복합니다.

 

은지는 우박수열을 좌표 평면 위에 꺾은선 그래프로 나타내보려고 합니다.

초항이 k인 우박수열이 있다면, x = 0일때 y = k이고,

다음 우박수는 x = 1에 표시합니다.

 

이렇게 만든 꺾은선 그래프를 정적분 하려고 합니다.

x에 대한 범위 [a, b]가 주어진다면,

처음부터 a만큼, 끝에서 b만큼 좌표사이의 넓이를 구하면 됩니다.

 

예를 들어,

좌표가 6개 주어졌고,

[a, b]가 [1, -2]라면,

x = 1부터 x = 5(배열은 0부터 시작하므로 6은 5번째이다)에서 2를 뺀 3까지의 넓이를 구하면 됩니다.

 

위 방법대로 주어진 ranges의 각 구간별 정적분(넓이)결과를 담아서 반환하면 됩니다.

 

제한 사항

• 2 <= k <= 10,000
• 1 <= ranges의 길이 <= 10,000
  • ranges의 원소는 [a, b] 형식이며,
  • 0 <= a < 200
  • -200 < b <= a
• 주어진 모든 입력값의 정적분 결과는 2^27을 넘지 않습니다.

 

성공 코드

/**
 * 우박수열 정적분
 * @param {number} k 우박수열의 첫 번째 수
 * @param {number[][]} ranges 정적분을 구할 범위
 * @returns {number[]} 정적분 결과
 */
function solution(k, ranges) {
  const hailstoneSequence = [{ x: 0, y: k }];
  const areaList = [];
  const result = [];

  /**
   * 우박수열 생성
   */
  const getHailstoneSequence = () => {
    let order = 0;
    let curNumber = k;

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

      order++;
      hailstoneSequence.push({ x: order, y: curNumber });
    }
  };

  /**
   * 넓이 리스트 생성
   */
  const getAreaList = () => {
    for (let i = 1; i < hailstoneSequence.length; i++) {
      const prevCoords = hailstoneSequence[i - 1];
      const curCoords = hailstoneSequence[i];

      const upperBase = prevCoords.y;
      const lowerBase = curCoords.y;
      const height = 1;
      const area = ((upperBase + lowerBase) * height) / 2;

      areaList.push(area);
    }
  };

  /**
   * 정적분 계산
   * @param {number} a 시작 인덱스
   * @param {number} b 끝 인덱스
   * @returns {number} 정적분 결과
   */
  const getIntegral = (a, b) => {
    const start = a;
    const end = hailstoneSequence.length - 1 + b;

    if (start > end) {
      return -1;
    }

    if (start === end) {
      return 0;
    }

    let sum = 0;
    for (let i = start; i < end; i++) {
      sum += areaList[i];
    }

    return sum;
  };

  /**
   * 결과 생성
   */
  const getResult = () => {
    for (const [a, b] of ranges) {
      const integral = getIntegral(a, b);

      result.push(integral);
    }
  };

  getHailstoneSequence();
  getAreaList();
  getResult();

  return result;
}

 

문제에 나온대로 그대로 구현하였다.

처음에 넓이를 구할 때,

반으로 나눠서 사각형과 삼각형의 넓이를 따로 구해서 더하려고 했는데,

사다리꼴 넓이 공식을 까먹고 있었기 때문이다...

사다리꼴 넓이 공식은 다음과 같다.

(윗 변 + 아랫 변) * 높이 / 2

여기서 윗 변과 아랫 변은 각각 y좌표이며,

높이는 1로 고정되어 있다.

 

특별히 미리 조건처리하면 좋을 것들은 다음과 같다.

• 시작점의 x좌표가 끝점의 x좌표보다 클 때
  • 유효하지 않으므로 -1을 반환한다.
• 시작점의 x좌표와 끝점의 x좌표와 같을 때
  • 넓이가 0이므로 0을 반환한다.

 

이 조건들만 미리 처리해주면,

굳이 불필요한 계산을 하지 않고 쉽게 답을 구할 수 있다.