억억단을 외우자

링크

https://school.programmers.co.kr/learn/courses/30/lessons/138475

문제

영우는 천하제일 암산대회를 앞두고 있습니다. 암산보다는 암기에 일가견이 있는 영우는 구구단을 확장하여 억억단을 만들고 외워버리기로 하였습니다.

억억단은 1억 x 1억 크기의 행렬입니다. 억억단을 외우던 영우는 친구 수연에게 퀴즈를 내달라고 부탁하였습니다.
수연은 평범하게 문제를 내봐야 영우가 너무 쉽게 맞히기 때문에 좀 어렵게 퀴즈를 내보려고 합니다. 적당한 수 e를 먼저 정하여 알려주고 e 이하의 임의의 수 s를 여러 개 얘기합니다. 영우는 각 s에 대해서 s보다 크거나 같고 e 보다 작거나 같은 수 중에서 억억단에서 가장 많이 등장한 수를 답해야 합니다. 만약 가장 많이 등장한 수가 여러 개라면 그 중 가장 작은 수를 답해야 합니다.

수연은 영우가 정답을 말하는지 확인하기 위해 당신에게 프로그램 제작을 의뢰하였습니다. e와 s의 목록 starts가 매개변수로 주어질 때 각 퀴즈의 답 목록을 return 하도록 solution 함수를 완성해주세요.

풀이

문제에 대한 해석이 가장 먼저 필요하다. 문제는 어렵게 적어놓았지만, 결과적으로 해석하면 start부터 e까지의 숫자들 중에서 약수의 개수가 가장 많고, 가장 작은 수를 찾으면 된다.

풀이를 할 때 e의 범위가 500만, starts의 최대 길이가 10만까지 나올 수 있으므로 시간복잡도가 제곱되는 상황이 나오면 시간 내에 문제를 해결하지 못하는 경우가 나오기 때문에 이것을 생각하면서 문제를 해결해야한다.

가장 중요한 것은 약수의 개수를 구하는 건데, 보통 약수의 개수는 반복문을 돌리며 선언된 변수로 나누어지는지 확인하거나, 제곱근의 값을 구해서 해당 값까지 나누어지면 count를 2를 증가시키는 등의 방식으로 구했는데 이 문제에서는 해당 방법만으로도 시간초과가 일어날 수 있기 때문에 시간을 줄이는 것이 가장 중요해서 관련된 공식을 사용해야한다.

for (let i = 1; i <= e; i++) {
  for (let j = 1; j <= e / i; j++) {
    count[i * j]++;
  }
}

이 방법으로 배열의 인덱스 번호와 그 값이 각각 어떤 수와 어떤 수의 약수의 개수가 된다.

이 문제는 시간 복잡도를 최대한으로 줄여서 문제를 풀이하는 것이 관건인데 관련되어 실패하는 코드들이 있다.

starts.map(el => {
	const slice = count.slice(el, e + 1)
	const maxIndex = slice.indexOf(Math.max(...slice))
   
	result.push(maxIndex + el)
})

위의 코드는 js가 지원하는 함수들을 사용해서 최대값을 가지는 인덱스를 구하는 식인데 Math.max의 부분에서 오류가 발생한다.

인자들의 e의 숫자가 작으면 크게 상관없이 간단하게 풀이가 가능한 코드지만, e의 수가 커지면 커질수록 Math.max에서 메모리 오버로 런타임 에러가 발생한다. 따라서 다른 식으로 slice 배열에서 최대값을 구해내야 한다.

starts.map(el => {
	const slice = count.slice(el, e + 1)
    const sort = [...slice].sort((a, b) => b - a)
	const maxIndex = slice.indexOf(sort[0])
   
	result.push(maxIndex + el)
})

위와 비슷한 방법으로 푸는 것인데 slice 배열의 최대값을 구하는 방식이 조금 다르다. 여기서는 sort를 통해서 내림차순 정렬을 하고 0번 인덱스의 값을 사용하는 방식인데 적어도 위의 코드와는 다르게 런타임 에러는 발생하지 않지만, sort의 과정이 생각보다 오래 걸리며 start의 길이가 길면 길수록 그 시간은 더 오래 걸리기 때문에 시간초과가 발생한다.

따라서 반복안에 반복이 최소화되는 코드를 구성해야한다.

아래의 풀이 코드에서는 새로운 배열 자체를 하나 만들어서 값들을 모두 e로 채워주었다. 그리고 뒤에서부터 계산을 해주면서 해당 인덱스 숫자가 가지는 약수의 개수가 max로 설정된 값보다 많은지 적은지에 따라서 연산을 하며 내려오면 O(n) = n의 과정으로 모든 숫자에 대해서 우리가 원하는 값을 구할 수 있다.

코드

function solution(e, starts) {
    const result = []
    let count = new Array(e + 1).fill(0)
    
    // 약수의 개수를 구하는 공식, O(n) = nlogn
    for (let i = 1; i <= e; i++) {
        for (let j = 1; j <= e / i; j++) {
            count[i * j]++;
        }
    }
    
    // start부터 e까지의 숫자들 중에서 가장 많은 약수의 개수를 가진 것 중에서 가장 앞에 있는 수를 찾는다.
    
    // 새로운 배열 자체를 만들어서 해당 숫자와 마지막 숫자까지의 약수개수를 가지는 배열을 생성.
    // sort 등등 다른 과정이 들어가게 될 경우에 e가 5백만이면 시간이 너무 오래걸림. 
    // 단순 계산만해봐도 e가 500만, start가 10만이면 총 5000억번의 과정이 필요하게 됨.
    // 따라서 해당 숫자부터 e 까지 약수의 개수가 어떻게 되는지 미리 계산을 하고 나중에 한번에 참조.
    let arr = new Array(e + 1).fill(count[e])
    let max = count[e]
    let index = e
    
    for(let i = e; i >= 0; i--) {
        if(count[i] >= max) {
            arr[i] = i
            max = count[i]
            e = i
        } else {
            arr[i] = e
        }
    }
    
    starts.map(el => {
        result.push(arr[el])
    })
  
    return result
}