🌈 시작하며

알고리즘 스터디가 있어 간만에 문제를 풀어보았어요 :)
이번 문제는 이전 문제 대비 비교적 쉬운 난이도인 억억단을 외우자였습니다.
결론부터 이야기를 하자면, 저는 DP로 풀었어요.
무엇보다 이 문제를 제대로 이해하면, DP가 가장 직관적이라는 생각이 들었습니다.

그렇다면, 어떻게 풀었는지 살펴볼까요? 😉

🚦 본론

설계 과정

우리가 보통 구구단을 하면 3 * 4 = 12 처럼 하나의 방정식이 나오죠.
이러한 방정식들의 모음이 좀 더 큰 단위로 표현되어, 곧 억억단이라는 게 나왔다고 볼 수 있겠어요.

이때 우리는 한 가지 힌트를 얻을 수 있습니다.

12라는 것은 3에서 나왔다면 무조건 4에서도 나온다는 것이죠!

Q. 이게 왜 힌트인가요? 😖

구구단에서 많이 나왔다는 것은, 결국 어떤 e 이하의 숫자에서의 곱셈 식의 결과가 해당 값이 되었다는 이야기입니다.
가령 예시에서 나온 e = 8일 때 8이 될 수 있었던 이유는 1을 곱할 때, 2를 곱할 때, 4를 곱할 때, 8을 곱할 때 나왔기 때문이죠.

오, 그렇다면 우리는 문제의 접근을 약수로부터 찾으면 되지 않을까요?

약수를 구하는 방법

약수를 구하는 방법은 정말 많습니다.
그 중 가장 직관적인 방법은, 저장할 배열을 만들어, 그곳에 약수를 직접 다 곱하는 방법입니다.

또한, 직관적일 뿐만 아니라 일일이 번거로운 계산을 하지 않기 때문에 약수를 구하는데 있어 효율적인 방법이기도 하죠.

이때, 1은 어차피 모든 곳에서 곱하기 때문에 처음부터 반영해주면, 최악의 경우 5000000만큼 연산을 줄일 수 있겠죠? 😉

따라서 다음과 같이 약수를 구해주는 로직을 생성해줍시다.
시간복잡도는 얼핏 대략적으로 따져보면 O(NlogN) 정도는 될 것 같아요. (정확하지는 않으나, 결국 제곱만큼 곱하는 로직이 반복되기 때문입니다.)

const counts = new Array(e + 1).fill(1); // 1 반영

for (let num = 2; num <= e; num += 1) {
  for (let divider = num; divider <= e; divider += num) {
    counts[divider] += 1;
  }
}

배열 안에 주어진 starts 내에서 최대 약수 개수를 가진 인덱스 값 찾기

여기에서 꽤나 골치 아프실 수 있었을 것 같아요.
하지만 여기서 DP를 사용한다면 문제를 굉장히 단순화시킬 수 있습니다.

DP로 문제 해결하기

사실 직관적으로 떠오르는 것이 무엇일까요? 바로 누적 합입니다.
일단 문제의 예시에서처럼 e = 8, starts = 1, 3, 7로 예시로 들어보겠습니다.

여기서 starts에 걸맞는 값을 풀이하면 다음과 같을 거에요.

const results = [
	`1~8 중 가장 약수가 많은 숫자 중 작은 숫자`, 
    `3~8 중 가장 약수가 많은 숫자 중 작은 숫자`, 
    `7~8 중 가장 약수가 많은 숫자 중 작은 숫자`
]

엇, 그런데 뭔가 좀 불편한 게 보이지 않나요?
바로 합이 겹치는 구간이 존재한다는 것입니다.

이러한 경우에는 DP를 사용하여 8~8에서의 조건에 맞는 값을 구하여 거꾸로 반영해주면 되지 않을까요?

바로 다음과 같이 말입니다.

const results = new Array(e + 1).fill(1);

for (let i = results.length - 1; i >= 0; i -= 1) {
  if (i === results.length - 1) {
    results[i] = i;
    continue;
  }

  const prevMaxIdx = results[i + 1];

  results[i] = counts[i] >= counts[prevMaxIdx] ? i : prevMaxIdx;
}

그러면 결과적으로 results[i]에는 start = i일 때 해당 구간에서 가장 약수가 많으면서도, 작은 값이 업데이트가 될 수 있습니다. (counts[i] >= counts[prevMaxIdx]이기 때문입니다.)

어떤가요?
결과값을 배열 형식으로 만들기 위해 얼핏 최소한 정렬을 해야할 것 같던 문제가, O(N)으로 해결되었습니다.
N = 5000000이라는 점에서 문제가 어려워보이지만, 막상 뜯어보면 매우 간단하고 별거 아닌 문제가 되었군요! 🚀

결과 코드

const solution = (e, starts) => {
  const counts = new Array(e + 1).fill(1);
  const results = new Array(e + 1).fill(0);
    
  for (let num = 2; num <= e; num += 1) {
    for (let divider = num; divider <= e; divider += num) {
      counts[divider] += 1;
    }
  }

  for (let i = results.length - 1; i >= 0; i -= 1) {
    if (i === results.length - 1) {
      results[i] = i;
      continue;
    }

    const prevMaxIdx = results[i + 1];

    results[i] = counts[i] >= counts[prevMaxIdx] ? i : prevMaxIdx;
  }

  return starts.map((start) => results[start]);
};

매우 빠르게 문제를 해결했군요! 🙆🏻

🚀 마치며

사실 저는 이 문제를 초반에 다소 헤맸어요.
아무래도 시간복잡도를 고려할 때 N = 5000000이라서 무조건 O(N)이내로 풀어야 한다고 생각했는데요.

결국 그렇게 고민하다, 설마 되겠어?하던 O(NlogN)으로 문제를 해결하니 매우 허탈했답니다 😖

앞으로는 일단 비슷한 시간복잡도라면 일단 트라이해보는 연습을 해봐야겠어요.
다들 즐거운 공부하시길 바라며. 이상!