[프로그래머스] 억억단을 외우자

문제 요약

각 시작점 s에 대해 [s, e] 범위에서 억억단에 가장 많이 등장하는 수를 구한다. 등장 횟수가 같다면 더 작은 수를 선택한다.

공식 제한에서 e는 최대 5,000,000이고, starts의 길이는 최대 100,000이다. 질문마다 구간 전체를 확인하면 많은 계산이 반복되므로, 모든 질문이 같은 끝점 e를 사용한다는 점을 활용한다.

핵심 아이디어

1. 등장 횟수는 약수의 개수다

억억단의 (i, j) 위치에는 i * j가 들어간다. 예를 들어 6이 등장하는 위치는 다음 네 곳이다.

1 * 6
2 * 3
3 * 2
6 * 1

6의 약수는 1, 2, 3, 6으로 4개다. 각 약수 d마다 (d, 6 // d)라는 위치가 하나씩 대응한다.

검사하는 수는 모두 500만 이하이므로, 두 인수도 억억단의 행과 열 범위인 1억을 넘지 않는다. 따라서 약수 개수를 그대로 등장 횟수로 사용할 수 있다.

2. 약수를 쌍으로 센다

d * k = number에서 d < k라면 (d, k)와 (k, d) 두 위치가 존재한다. 반면 d == k인 제곱수는 (d, d) 한 위치만 센다.

작은 인수 d를 1부터 isqrt(e)까지 순회하면서 다음처럼 계산한다.

• d * d에는 1을 더한다.
• d * (d + 1), d * (d + 2), ...에는 2씩 더한다.

모든 인수 쌍의 작은 쪽만 순회하므로 같은 쌍을 중복 계산하지 않는다. isqrt(e)는 제곱근의 정수 부분을 정확하게 구한다.

3. 뒤에서부터 구간별 정답을 저장한다

best[s]를 [s, e]에서 등장 횟수가 가장 많고, 동점이면 가장 작은 수라고 정의한다.

best[s + 1]을 이미 안다면, 새로 추가되는 s와 그 값만 비교하면 된다.

count[s] >= count[best[s + 1]]이면 best[s] = s
그 외에는 best[s] = best[s + 1]

오른쪽에서 왼쪽으로 확인하므로 현재 수가 기존 후보보다 작다. 따라서 동점일 때도 현재 수로 갱신하도록 >=를 사용해야 한다.

풀이 과정

1. 약수 쌍을 이용해 1부터 e까지 등장 횟수를 구한다.
2. e부터 min(starts)까지 역순으로 순회한다.
3. 현재 수와 지금까지의 최적 후보를 비교해 best에 저장한다.
4. 입력 순서대로 best[s]를 반환한다.

Python 코드

from math import isqrt


def solution(e, starts):
    count = [0] * (e + 1)

    for divisor in range(1, isqrt(e) + 1):
        square = divisor * divisor

        # (divisor, divisor)는 한 위치만 차지한다.
        count[square] += 1

        # 서로 다른 인수의 쌍은 순서를 바꾼 두 위치에 등장한다.
        for number in range(square + divisor, e + 1, divisor):
            count[number] += 2

    best = [0] * (e + 1)
    candidate = e

    for number in range(e, min(starts) - 1, -1):
        # 동점이면 더 작은 수인 number를 선택한다.
        if count[number] >= count[candidate]:
            candidate = number

        best[number] = candidate

    return [best[start] for start in starts]

예시

e = 8, starts = [1, 3, 7]일 때 등장 횟수와 구간별 정답은 다음과 같다.

수	등장 횟수	이 수부터 8까지의 정답
1	1	6
2	2	6
3	2	6
4	3	6
5	2	6
6	4	6
7	2	8
8	4	8

[1, 8]과 [3, 8]에서는 6과 8이 각각 4번 등장한다. 동점이므로 더 작은 6을 선택한다. [7, 8]에서는 8이 더 많이 등장한다.

따라서 반환값은 [6, 6, 8]이다.

시간 복잡도

E = e, Q = len(starts)라고 하자.

약수 계산의 내부 반복 횟수는 작은 인수 d마다 대략 E / d - d이다. 이를 제곱근까지 합하면 O(E log E)이다. 각 수마다 모든 약수를 따로 탐색하는 O(E * sqrt(E)) 방식보다 계산량을 줄인다.

• 시간 복잡도: O(E log E + Q)
• 공간 복잡도: 반환 배열을 포함해 O(E + Q)

뒤에서부터 정답을 계산하는 데는 O(E), 각 질문에 답하는 데는 O(1)이 걸린다. min(starts)보다 작은 시작 구간은 계산하지 않지만, 이 코드의 두 배열은 모두 E + 1 크기로 할당된다.

정리

곱셈표의 등장 횟수를 약수 개수로 바꾼 뒤, 끝점이 같은 구간들의 정답을 뒤에서부터 계산한다. 제곱수는 한 번만 세고, 동점 비교에 >=를 사용하는 것이 구현의 핵심이다.