[프로그래머스] 억억단을 외우자 - 자바스크립트

문제

프로그래머스

 

처음에 문제 조건을 재해석해야하고, 시간 초과도 신경써야 하는 문제다.

특히 시간 초과를 잘 생각하면서 설계해보자.

e의 범위가 500만인데, 각 케이스마다 모두 조회를 해야한다면.. 기계가 힘들어한다.

---

코드

function solution(e, starts) {
  const denominators = getAllDenominators(e);
  const lowestMaxNumArr = getLowestMaxNumArr(denominators, e);

  return starts.map((s) => lowestMaxNumArr[s]);
}

function getAllDenominators(size) {
  const result = new Array(size + 1).fill(2);
  result[0] = 0;
  result[1] -= 1;

  for (let i = 2; i <= size; i++) {
    for (let j = 2, end = Math.floor(size / i); j <= end; j++) {
      result[i * j]++;
    }
  }

  return result;
}

function getLowestMaxNumArr(arr, size) {
  const lowestMaxNumArr = new Array(size + 1).fill(0);
  lowestMaxNumArr[size] = size;

  for (let i = size - 1; i > 0; i--) {
    const cur = arr[i];
    const prev = arr[lowestMaxNumArr[i + 1]];

    lowestMaxNumArr[i] = cur >= prev ? i : lowestMaxNumArr[i + 1];
  }

  return lowestMaxNumArr;
}

 

---

풀이

여러번의 시행착오 끝에 코드가 짧아져 다행이다.

 

문제 조건

천하제일 암산대회.  

억억단은 1억*1억의 행렬이다.  

적당한수 e를 먼저 알려주고, e이하의 수 s를 여러번 말해준다.  

우리는 s마다의 정답 x를 구해야 하는데 각 s에 대해 s<=x<=e인 수 중, 억억단에 가장 많이 등장한 수가 x이다.

가장 많이 등장한 수가 여러개면, 가장 작은 수를 답한다.

 

제한사항

1 <= e <= 5,000,000

1 <= starts.length <= min(e, 100,000)

1 <= starts 원소 <= e

 

풀이방향 요약

1. [1 ~ e] 구간 각 숫자 별로 빈도수를 구한다.

2. starts 배열을 순회하면서 [s ~ e] 구간에서 각 구간별로 빈도수가 최대이면서, 가장 작은 값을 구한다.

3. 출력한다.

 

풀이방향 상세설명

e가 최대 500만이므로, 시간복잡도를 가장 신경써야 한다.

특정 숫자 b가 억억단에서 몇번 등장했는지 어떻게 카운트할 수 있을까?

 

문제 예시에 힌트가 있다.

1번등장 : 1, 2번등장 : 2,3,5,7, 3번등장 : 4

이들의 공통점은 등장횟수 = 약수의 갯수다. 억억단에서의 등장 횟수를 b의 약수의 갯수로 취급할 수 있다.

 

그렇다면 우선 1~e까지의 약수의 갯수를 각자의 방법대로 구한다.

(= 약수 갯수 구하는 방법은 많지만, 시간초과를 생각하며 문제에 적당한 것을 찾아보자.)

 

그 다음엔 s~e 범위에서 약수의 갯수가 가장 많으면서, 가장 작은 숫자를 찾아야 한다.

e가 작은 숫자라면 slice + Math.max를 활용해도 되겠지만, 시간초과가 발생하지 않을까?

여기서도 약수의 갯수를 미리 구해둔것 처럼, 무언가를 미리 구한 뒤 바로 써먹으면 좋을 것 같다.

 

각 구간 [s ~ e]에서, s는 변하지만 e는 고정되어 있다.

그렇다면 [1 ~ e]의 정답은 1번 인덱스에, [25700 ~ e]는 25700번 인덱스에 저장해두면 쓰기 좋아보인다.

이를 위해선 배열의 끝(e)부터 1번 인덱스까지 역순으로 순회하면서, 약수의 갯수가 가장 많은 최솟값을 기록하면 된다.

 

이정도 이해했다면 코드를 짜러가면 되겠다. 물론 밑에 주석을 첨부한 코드도 첨부해뒀다.

---

주석을 첨부한 코드

function solution(e, starts) {
  // 약수의 갯수들, 구간별 최대약수갯수인 최솟값을 구한뒤에
  // s에 대응하는 최솟값들을 출력하고 끝난다.
  const denominators = getAllDenominators(e);
  const lowestMaxNumArr = getLowestMaxNumArr(denominators, e);
  const answer = starts.map((s) => lowestMaxNumArr[s]);

  return answer;
}

/**
 * 모든 약수를 구한다. 각자 찾은 방법대로 구하자.
 * (e에 따른 시간복잡도는 고려해야한다.)
 * 약수 카운팅중에 [1*자기자신]을 건너뛰고 싶어서 기본값을 2로 설정했다.
 */
function getAllDenominators(size) {
  const result = new Array(size + 1).fill(2);
  result[0] = 0;
  result[1] -= 1;

  for (let i = 2; i <= size; i++) {
    for (let j = 2, end = Math.floor(size / i); j <= end; j++) {
      result[i * j]++;
    }
  }

  return result;
}

/**
 * lowestMaxNumArr의 인덱스 k는 [k ~ e] 구간에서의 약수의 갯수가 가장 많은 최솟값이다.
 * 인덱스 e부터 순회하면서, 현재의 약수의 갯수가 앞선 인덱스의 약수의 갯수보다 크거나 같다면 갱신한다.
 * 같을 때는 현재 인덱스가 앞선 최솟값 인덱스보다 더 최솟값이므로, 꼭 갱신해줘야한다.
 */
function getLowestMaxNumArr(arr, size) {
  const lowestMaxNumArr = new Array(size + 1).fill(0);
  lowestMaxNumArr[size] = size;

  for (let i = size - 1; i > 0; i--) {
    const cur = arr[i];
    const prev = arr[lowestMaxNumArr[i + 1]];

    lowestMaxNumArr[i] = cur >= prev ? i : lowestMaxNumArr[i + 1];
  }

  return lowestMaxNumArr;
}