프로그래머스 코딩테스트 - 억억단을 외우자

문제 설명

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

프로그래머스

e	starts	result
8	[1,3,7]	[6,6,8]

 

요약: 억억단 중 s단에서 s보다 크고 e보다 작은 수의 횟수를 구해 가장 많이 등장한 수 중 가장 작은 수를 구한다.

해결 방법

기본 아이디어

모든 곱셈 결과가 필요하지 않다. 우리는 곱셈 결과 중 e보다 작은 수만 필요한 것이다.

따라서 억억단을 진행할 때 e보다 작은 수만 구해줘도 상관이 없다.

위의 그림을 보면 규칙을 찾을 수 있다. e보다 작은 수를 구하려면 우리는 1단 부터 e단까지만 진행해줘도 된다. 또한, 억억단을 끝까지 계산하지 않고 (e / 현재 단) 까지 해주면 우리는 e보다 작은 수의 횟수를 구할 수 있다.

 

그렇게 나온 억억단 코드는 다음과 같다.

const multi = Array.from({length: e}, () => 0)

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

 

이제 starts를 순회하며 s보다 크고 e보다 작으면서 가장 많이 나온 수 중 가장 작은 수를 구하면 된다.

아이디어 1

• starts를 순회하면서
  • multi를 s부터 e까지 쪼갠 후 그 안에서 최댓값 구하기
  • 최댓값과 동일한 것 중 s보다 큰 가장 작은 수 구하

코드

return starts.map((s) => {
	if (s === e) return e
        
	const max = Math.max(...multi.slice(s-1))
	return multi.findIndex((m, idx) => m === max && idx + 1 >= s) + 1
})

문제점

테스트 9, 10에서 런타임 에러가 났다.

뭐가 문제였을까....

런타임 에러가 나는 것으로 봐서는 시간이 오래걸린 문제가 아니라 배열에 잘못된 인덱스로 접근한 것 같은데..

아이디어 2

starts를 순회할 때 최댓값을 구하지 말고 미리 최댓값을 구한 다음 starts를 순회하도록 수정해봤다.

 

새로운 배열을 생성해 multi의 역순으로 순회하며 최댓값을 구해주면 된다.

역순으로 순회하는 이유는 (7, 8)의 최댓값은 (6, 8)의 최댓값에 포함되기 때문이다.

그렇게 작성한 코드는 아래와 같다.

코드

function solution(e, starts) {
    var answer = [];
    const multi = Array.from({length: e}, () => 0)
    const maxIdx = []
    for (let i = 1; i <= e; i++) {
        for(let j = 1; j <= e / i; j++) {
            multi[i * j - 1] += 1
        }
    }
    
    let max = 0, maxAdd = e;
    
    for(let i = e; i > 0; i--) {
        const count = multi[i - 1];
        if (max <= count) {
            maxAdd = i;
            max = count;
        }
        maxIdx.push(maxAdd);
    }
    
    return starts.map((s) => maxIdx[e - s])
}

결과

말끔히 통과v