📌 문제
📌 접근
- 어떻게 효율성을 높여서 시간복잡도를 줄일 수 있을까?
📌 코드
js
1차 시도
function solution(n) {
var answer = 0;
for(var i=2; i<=n; i++){
let s = 0;
for(var j=1; j<=i; j++) {
if(i%j == 0) s++;
}
if(s==2) answer++;
}
return answer;
}
채점 결과
정확성: 56.3
효율성: 0.0
합계: 56.3 / 100.0
테스트케이스 10~14도 시간초과...
2차 시도
function solution(n) {
var sosu = [2]
if(n>2){
for(var num=3; num<=n; num+=2){
var temp =0;
var i=0;
while(i<sosu.length){
if(num%sosu[i] !== 0){
temp++
}
else {
temp = 0;
break;
}
i++;
}
if(temp !== 0) sosu.push(num);
}
}
return sosu.length;
}
채점 결과
정확성: 75.0
효율성: 0.0
합계: 75.0 / 100.0
범위를 조금 줄여서 테스트케이스는 모두 잘 넘어갔지만 효율성 케이스 1~4 모두 시간초과가 나왔다..
3차 시도
function solution(n) {
const sosu = [2]
if(n>2){
for(var num=3; num<=n; num+=2){
if(num==3 || num==5 || num==7) sosu.push(num);
else if(num>7){
sosu.push(num)
for(var i=1; i<sosu.length-1; i++){
if(num%sosu[i]==0){
sosu.pop(num);
break;
}
}
}
}
}
return sosu.length;
}
테스트 10 〉 통과 (1153.23ms, 33.2MB)
테스트 11 〉 통과 (9383.79ms, 34MB)
테스트 12 〉 통과 (1405.79ms, 33MB)
효율성 테스트
테스트 1 〉 실패 (시간 초과)
테스트 2 〉 실패 (시간 초과)
테스트 3 〉 실패 (시간 초과)
테스트 4 〉 실패 (시간 초과)
2차시도와 같은 결과..
4차 시도
function solution(n) {
let sosu = Array.from({length : n-1}, (v,i) => i+2);
for(var i=0; sosu[i]<=Math.sqrt(n); i++){
sosu = sosu.filter(x => x==sosu[i] || x%sosu[i]);
console.log(sosu);
}
return sosu.length;
}
테스트 10 〉 통과 (196.47ms, 62.4MB)
테스트 11 〉 통과 (807.62ms, 70.5MB)
테스트 12 〉 통과 (232.20ms, 59.8MB)
효율성 테스트
테스트 1 〉 실패 (시간 초과)
테스트 2 〉 실패 (시간 초과)
테스트 3 〉 실패 (시간 초과)
테스트 4 〉 실패 (시간 초과)
- 처음에 2부터 n까지의 모든 수의 배열을 만든다. (모든 수를 소수로 봄)
- 처음 숫자부터 n의 제곱근까지 반복하는데, 처음 숫자는 그대로 두고 필터링한다.
(i=0) sosu = [2,3,5,7,9,11 ...]
(i=1) sosu = [2,3,5,7,11 ...]
filter(x => x==sosu[i] || x%sosu[i]) 로 이전 시도들과 비교하여 굉장히 간결해졌고 에라토스테네스의 체와 흡사한 알고리즘이지만 이미 소수로 판정된 숫자가 배열안에 남아있기 때문에 시간복잡도가 한계가 있었던 듯..
5차 시도
function solution(n) {
let temp = Array.from({length : n-1}, (v,i) => i+2);
const sosu = [];
while(temp[0]<=Math.sqrt(n)){
sosu.push(temp[0]);
temp = temp.filter(x => x%temp[0]);
}
return sosu.length + temp.length;
}
테스트 10 〉 통과 (171.38ms, 59.5MB)
테스트 11 〉 통과 (714.20ms, 70.3MB)
테스트 12 〉 통과 (197.79ms, 61.4MB)
효율성 테스트
테스트 1 〉 실패 (시간 초과)
테스트 2 〉 실패 (시간 초과)
테스트 3 〉 실패 (시간 초과)
테스트 4 〉 실패 (시간 초과)
- 하나의 빈 배열을 만들고 처음 빼준 숫자를 넣는 것을 반복, 두 배열의 길이를 더해주는 전략...이었지만 이것도 실패 (그래도 확실히 점점 실행시간이 줄어들고 있었다)
6차 시도
function solution(n) {
let sosu = Array.from({length : n+1}, v => true);
for(var num = 2; num<=Math.sqrt(n); num++){
if(sosu[num]){
for(var i=num*num; i<=n; i+=num){
sosu[i] = false;
}
}
}
const result = sosu.filter(x => x == true);
return result.length - 2 ;
}
테스트 10 〉 통과 (50.11ms, 34.6MB)
테스트 11 〉 통과 (146.01ms, 39.9MB)
테스트 12 〉 통과 (56.45ms, 34.8MB)
효율성 테스트
테스트 1 〉 통과 (156.41ms, 40.6MB)
테스트 2 〉 통과 (148.64ms, 40.4MB)
테스트 3 〉 통과 (149.59ms, 40.5MB)
테스트 4 〉 통과 (147.36ms, 40.3MB)
에라토스테네스의 체를 사용하니... 솔직히 내 코드와 실행시간이 크게 다르지 않을거라고 생각했는데 엄청난 차이가 있었다.
python
def solution(n):
sosu = [True] * (n+1)
for num in range(2, int(n**0.5)+1) :
if sosu[num] :
for i in range(num*num, n+1, num) :
sosu[i] = False
result = [x for x in range(2,n+1) if sosu[x]==True]
return len(result)
테스트 10 〉 통과 (37.53ms, 13.2MB)
테스트 11 〉 통과 (124.00ms, 19.6MB)
테스트 12 〉 통과 (41.83ms, 13.6MB)
효율성 테스트
테스트 1 〉 통과 (142.66ms, 20.1MB)
테스트 2 〉 통과 (126.61ms, 19.9MB)
테스트 3 〉 통과 (131.63ms, 20MB)
테스트 4 〉 통과 (130.91ms, 19.9MB)
✍ 메모
위키백과 - 에라토스테네스의 체 https://ko.wikipedia.org/wiki/%EC%97%90%EB%9D%BC%ED%86%A0%EC%8A%A4%ED%85%8C%EB%84%A4%EC%8A%A4%EC%9D%98_%EC%B2%B4
filter()
js filter() 예제
const arr = [1,2,3,4,5,6,7,8,9,10]
arr.filter(x => x%2)
// [1,3,5,7,9]
arr.filter(x => x%2 != 0)
// [1,3,5,7,9]
arr.filter(x => x==2 || x%2)
// [1,2,3,5,7,9]
달리는 중!