코딩테스트 연습 / 연습문제 / 소수 찾기 / JAVA

 

문제 설명

 

1부터 입력받은 숫자 n 사이에 있는 소수의 개수를 반환하는 함수, solution을 만들어 보세요.

소수는 1과 자기 자신으로만 나누어지는 수를 의미합니다.
(1은 소수가 아닙니다.)

 

제한 조건

• n은 2이상 1000000이하의 자연수입니다.

 

입출력 예

n	result
10	4
5	3

 

입출력 예 설명

 

입출력 예 #1

1부터 10 사이의 소수는 [2,3,5,7] 4개가 존재하므로 4를 반환

 

입출력 예 #2
1부터 5 사이의 소수는 [2,3,5] 3개가 존재하므로 3를 반환

 

 

---

정답

import java.util.ArrayList;
import java.util.Iterator;
import java.util.List;

class Solution {
      public int solution(int n) {
          int answer = 0;
          int[] number = new int[n+1];
          
          for(int i=2; i<=n; i++) {
              number[i] = i;
          }
          
          for(int i=2; i<=n; i++) {
              if(number[i]==0) continue;
              
              for(int j= 2*i; j<=n; j += i) {
                  number[j] = 0;
              }
          }
          
          for(int i=2; i<=n; i++) {
              if(number[i]!=0) {
                  answer++;
              }
          }
          
          return answer;
      }
    }

---

오류

2020/04/10

class Solution {
  public int solution(int n) {
      int answer = 0;
      
      for(int i=2; i<=n; i++){
          int cnt = 0;
          for(int j=2; j<i; j++){
              if(i % j == 0) cnt++;
          }
          if(cnt == 0) answer++;
      }
      return answer;
  }
}

코드를 다음과 같이 짰으나 효율성 테스트를 통과하지 못하였다. 시간초과가 뜬다.

그래서 다음과 같이 바꿔봤다.

애초에 소수가 아니면 반복문을 끝까지 돌리지 말고 break를 거는 것이다.

1과 자기자신으로 나누어지는 카운트를 계산하지말고 처음부터 소수가 아닌것은 break해버리는 것이다.

 

class Solution {
  public int solution(int n) {
      int answer = 0;
      
      for(int i=2; i<=n; i++){
          
          int cnt = 2;
          for(int j=2; j<i; j++){
              if(i % j == 0) break;
              cnt++;
          }
          if(cnt == i) answer++;
      }
      return answer;
  }
}

그러나 여전히 시간초과가 뜬다.. 이 전보다 한문제는 더 통과한 정도이다.

이제는 도저히 내 머리로 해결할 수가 없어 다른 개발자 분들이 작성한 코드를 살펴보았다.

 

[Java][프로그래머스][Level 1] 소수 찾기 - 3가지 방법 이용

방법은 "에라토스테네스의 체"를 이용하는 것이라고 한다.

나는 이과임에도 불구하고 에라토스테네스를 처음 들어보았다.(학창시절 공부를 열심히 안했다)

그래서 일단 무작정 써보았다. 방법은 다음과 같다고 한다.

 

1. 2부터 n까지의 모든 수를 나열한다.

2. 2 ~ 10까지의 숫자(정확히는 n의 제곱근 전까지라는데 잘 모르겠다) 중 소수를 찾아 해당 소수의 배수를 모두 지운다.

 

그런데 막상 코드로 짜려니까 또 겁이난다.

소수를 찾는것 까지는 괜찮은데 배수를 지우라니?? 배열이 아닌 다른 자료구조를 사용해야되는건가?

주남2님은 다음과 같은 문제에 대해서 모든 소수의 배수를 0으로 치환하셨다.(정확한 정보는 위의 링크를 찾아가보면 된다)

 

그런데 배열 크기만큼 검사해야된다는 것 만큼은 변함이 없었다.

그래서 문뜩 리스트로 구현해보고 싶어져 다음과 같이 짰다.

 

import java.util.ArrayList;
import java.util.Iterator;
import java.util.List;

class Solution {
  public int solution(int n) {
       int answer = 0;
	      
	      List<Integer> list = new ArrayList<Integer>();
	      for(int i=1; i<=n; i++){
	          list.add(i);
	      }
	       
	      for(int i=2; i<=list.size(); i++){
	          for(int j=2*i; j<=n; j+=i){
	        	  for (Iterator<Integer> iter = list.iterator(); iter.hasNext(); ) {
	    	    	  Integer o = iter.next();
	    	    	  if(o == j) iter.remove();
	    	      }
	          }
	      }

	      list.remove(1);
	      
	      answer = list.size();
	      return answer;
  }
}

 

하지만 여전히 시간초과가 난다.

Iterator가 시간을 많이 잡아먹는건지 정확한 이유는 잘 모르겠다.

나중에 시간나면 한번 공부해 보아야 할 내용인 것 같다.