JavaScript_최소값과 합을 구하는 알고리즘에 대한 고찰 (작성중)

https://www.acmicpc.net/problem/2581

2581번: 소수

 

* min이상 max이하의 소수의 합을 구하는데, 그 중에서 최소값도 구하기

→ sum += k 를 할건데,

 조건을 만족하는 첫 번째 k 값만 primeMin으로 set하고,

 loop를 계속 돌려야 한다.

 

 

 

방법1) 내가 생각해낸 방법

: 첫 번째 소수를 구하면 그 값을 primeMin에 저장하고 break한 후,

primeMin+1부터 다시 loop를 돌린다.

 

단점

- 체크했던 수를 또 체크하지는 않지만,

  코드의 중복 (sum += k) 이 생긴다.

function solution(min, max) {
    var sum = 0;
    for (var j = min; j <= max; j++) {
        if (isPrime(j)) {
            var primeMin = j;
            sum = + j;
            break;
        }
    }
    for (var k = primeMin + 1; k <= max; k++) {
        if (isPrime(k)) sum += k;
    }
}

 

 

 

방법2) minkyung1님의 코드를 참고해서 고쳐본 것

: 문제에서 max의 최대값이 10000이었으므로,

primeMin = 10000+1로 설정하고,

k가 소수일 경우, k<primeMin이면 primeMin=k로 설정한다.

 

이 때 설정한 값은 소수 중 최소값이므로,

그 후부터 검출되는 소수는 그것보다 클 수 밖에 없다.

그래서 k < primeMin 은 충족될 수 없다.

그러므로 처음에 최소값으로 설정된 primeMin값이 계속 유지된다.

 

단점

- n의 최대값이 주어지지 않는다면?

 

function solution(min, max) {
    var primeMin = 10001; // n의 최대값+1
    var sum = 0;
    for (var k = min; k <= max; k++) {
        if (isPrime(k)) {
            sum += k;
            if (k < primeMin) primeMin = k;
        }
    }
}

 

 

 

방법3) lss3070님의 코드를 참고해서 고쳐본 것

: boolean 값을 가지는 check라는 변수를 false로 설정하고,

첫 소수를 k로 설정한 후에 check 값을 true로 바꿔서

if문이 계속 false가 되게 한다.

 

단점

- if문을 계속 체크해야 한다.

 

function solution(min, max) {
    var check = false;
    var primeMin = 0;
    var sum = 0;
    for (var k = min; k <= max; k++) {
        if (isPrime(k)) {
            if (check == false) {
                primeMin = k;
                check = true;
            }
            sum += k;
        }
    }
}

 

 

 

※ 아래 코드는 공통이어서 생략했다.

 

    if (sum == 0) {

        console.log(-1);

        return

    } else {

        console.log(sum);

        console.log(primeMin);

    }

 

 

https://modoocode.com/246

모두의 알고리즘 - 1. 어떤 알고리즘이 효율적인가?