잘못된 정보가 있다면, 꼭 댓글로 알려주세요(비로그인 익명도 가능).

여러분의 피드백이 저와 방문자 모두를 올바른 정보로 인도할 수 있습니다.

감사합니다. -현록

후원해주실 분은 여기로→

현록의 기록저장소

[Lv2] 소수 만들기 본문

Problem Solving/programmers

[Lv2] 소수 만들기

현록 2019. 4. 15. 22:44

https://programmers.co.kr/learn/challenges

 

프로그래밍 강의 | 프로그래머스

기초부터 차근차근, 직접 코드를 작성해 보세요.

programmers.co.kr

문제 설명

 

주어진 숫자 중 3개의 수를 더했을 때 소수가 되는 경우의 개수를 구하려고 합니다. 숫자들이 들어있는 배열 nums가 매개변수로 주어질 때, nums에 있는 숫자들 중 서로 다른 3개를 골라 더했을 때 소수가 되는 경우의 개수를 return 하도록 solution 함수를 완성해주세요.

 

제한사항

  • nums에 들어있는 숫자의 개수는 3개 이상 50개 이하입니다.
  • nums의 각 원소는 1 이상 1000 이하의 자연수이며, 중복된 숫자가 들어있지 않습니다.

입출력 예

nums result
[1,2,3,4] 1
[1,2,7,6,4] 4

 

입출력 예 설명

입출력 예 #1
[1,2,4]를 이용해서 7을 만들 수 있습니다.

입출력 예 #2
[1,2,4]를 이용해서 7을 만들 수 있습니다.
[1,4,6]을 이용해서 11을 만들 수 있습니다.
[2,4,7]을 이용해서 13을 만들 수 있습니다.
[4,6,7]을 이용해서 17을 만들 수 있습니다.

 

 

 

풀이 전략은 주어진 배열에서 3가지 합을 이용해서 만들 수 있는 모든 수를 저장해두고,

(합이 같더라도(중복), 그 합을 만들기 위해 쓰여진 애들은 다르기 때문에, 중복 포함하여 저장합니다.

원하는게 소수의 갯수가 아니라 소수를 만들 수 있는 경우의 수이기 때문.)

 

그 중 가장 큰 수를 꺼내서, 에라토스테네스의 체를 이용하여 소수의 구분자를 만들고,

에라토스테네스의 체: [Coding Quiz/programmers] - [Lv1] 소수의 합, 소수 찾기

 

소수를 구분자를 이용해서 소수의 수를 셀겁니다.

 

중복도 저장해둘 건데 최댓값은 알고싶으니.. 내림차순우선순위큐로 할 생각입니다.

 

 

아래는 배열에서 n가지 수의 가능한 모든 조합들을 활용하는 방법.

int answer;

public void set(int[] numbers, int[] check, int total, int count, int sum, int goal) {
	if(count==total) {
		if(sum==goal) answer++;
		return;
	} else if(count+1<=total) {
		int start = -1;
		for(int i=0;i<check.length;i++) {
			if(check[i]==3) {
				start = i;
				break;
			}
		}
		for(int i=start+1;i<check.length;i++) {
			if(check[i]==0 && i>0 && check[i-1]>0) {
				if((count+1)+(check.length-1-i)<total) break;
				check[i] = 1;
				set(numbers, check, total, count+1, sum+numbers[i], goal);
				if(check[i]==1) check[i] = 2;
			}
		}
		boolean firstRemove = false;
		for(int j=start+1;j<check.length;j++) {
			if(!firstRemove && check[j]==1) {
				check[j]=4;
				firstRemove = true;
			}
			else if(check[j]<3) check[j]=0;
		}
	}
}

public int solution(int[] numbers) {
	Arrays.sort(numbers);
	int[] check = new int[numbers.length];
	answer = 0;
	for(int i=1;i<=check.length;i++) {
		for(int j=0;j+i-1<check.length;j++) {
			Arrays.fill(check, 0);
			check[j] = 3;
			set(numbers, check, i, 1, numbers[j], 100);
		}
	}
	return answer;
}

 

시작값은 3으로 시작,

0인 애들을 1로 바꾸면서 사용, 호출 후 2로 바꾸면서 쓴 표시.

한번 for가 돌면 처음 만나는 1에 대해서만 4로 바꾸고, 나머지는 0으로 초기화.(3미만으로 해야 3을 안건드림)

 

3은 초기값, 4는 참여하지 않고 건너 뛰게(0이 아니라 안잡히고 3이상이라 함수내 초기화도 안됨), 

1은 이번에 사용, 2는 이번사용이 끝남.

 

함수 바깥에서 함수 시작 위치를 따로 3으로 잡음.

전체를 0으로 초기화하는 init함수를 둠.

 

경과를 보면,

더보기

3과 1로 표시된 칸만 계산에 포함된다.

1개▼

[3, 0, 0, 0, 0, 0, 0, 0] 

[0, 3, 0, 0, 0, 0, 0, 0] 

[0, 0, 3, 0, 0, 0, 0, 0] 

[0, 0, 0, 3, 0, 0, 0, 0] 

[0, 0, 0, 0, 3, 0, 0, 0] 

[0, 0, 0, 0, 0, 3, 0, 0] 

[0, 0, 0, 0, 0, 0, 3, 0] 

[0, 0, 0, 0, 0, 0, 0, 3] 

2개▼

[3, 1, 0, 0, 0, 0, 0, 0] 
[3, 2, 1, 0, 0, 0, 0, 0] 
[3, 2, 2, 1, 0, 0, 0, 0] 
[3, 2, 2, 2, 1, 0, 0, 0] 
[3, 2, 2, 2, 2, 1, 0, 0] 
[3, 2, 2, 2, 2, 2, 1, 0] 
[3, 2, 2, 2, 2, 2, 2, 1] 
[0, 3, 1, 0, 0, 0, 0, 0] 
[0, 3, 2, 1, 0, 0, 0, 0] 
[0, 3, 2, 2, 1, 0, 0, 0] 
[0, 3, 2, 2, 2, 1, 0, 0] 
[0, 3, 2, 2, 2, 2, 1, 0] 
[0, 3, 2, 2, 2, 2, 2, 1] 
[0, 0, 3, 1, 0, 0, 0, 0] 
[0, 0, 3, 2, 1, 0, 0, 0] 
[0, 0, 3, 2, 2, 1, 0, 0] 
[0, 0, 3, 2, 2, 2, 1, 0] 
[0, 0, 3, 2, 2, 2, 2, 1] 
[0, 0, 0, 3, 1, 0, 0, 0] 
[0, 0, 0, 3, 2, 1, 0, 0] 
[0, 0, 0, 3, 2, 2, 1, 0] 
[0, 0, 0, 3, 2, 2, 2, 1] 
[0, 0, 0, 0, 3, 1, 0, 0] 
[0, 0, 0, 0, 3, 2, 1, 0] 
[0, 0, 0, 0, 3, 2, 2, 1] 
[0, 0, 0, 0, 0, 3, 1, 0] 
[0, 0, 0, 0, 0, 3, 2, 1] 
[0, 0, 0, 0, 0, 0, 3, 1]

3개▼
[3, 1, 0, 0, 0, 0, 0, 0] 
[3, 1, 1, 0, 0, 0, 0, 0] 
[3, 1, 2, 1, 0, 0, 0, 0] 
[3, 1, 2, 2, 1, 0, 0, 0] 
[3, 1, 2, 2, 2, 1, 0, 0] 
[3, 1, 2, 2, 2, 2, 1, 0] 
[3, 1, 2, 2, 2, 2, 2, 1] 
[3, 4, 1, 0, 0, 0, 0, 0] 
[3, 4, 1, 1, 0, 0, 0, 0] 
[3, 4, 1, 2, 1, 0, 0, 0] 
[3, 4, 1, 2, 2, 1, 0, 0] 
[3, 4, 1, 2, 2, 2, 1, 0] 
[3, 4, 1, 2, 2, 2, 2, 1] 
[3, 4, 4, 1, 0, 0, 0, 0] 
[3, 4, 4, 1, 1, 0, 0, 0] 
[3, 4, 4, 1, 2, 1, 0, 0] 
[3, 4, 4, 1, 2, 2, 1, 0] 
[3, 4, 4, 1, 2, 2, 2, 1] 
[3, 4, 4, 4, 1, 0, 0, 0] 
[3, 4, 4, 4, 1, 1, 0, 0] 
[3, 4, 4, 4, 1, 2, 1, 0] 
[3, 4, 4, 4, 1, 2, 2, 1] 
[3, 4, 4, 4, 4, 1, 0, 0] 
[3, 4, 4, 4, 4, 1, 1, 0] 
[3, 4, 4, 4, 4, 1, 2, 1] 
[3, 4, 4, 4, 4, 4, 1, 0] 
[3, 4, 4, 4, 4, 4, 1, 1] 
[0, 3, 1, 0, 0, 0, 0, 0] 
[0, 3, 1, 1, 0, 0, 0, 0] 
[0, 3, 1, 2, 1, 0, 0, 0] 
[0, 3, 1, 2, 2, 1, 0, 0] 
[0, 3, 1, 2, 2, 2, 1, 0] 
[0, 3, 1, 2, 2, 2, 2, 1] 
[0, 3, 4, 1, 0, 0, 0, 0] 
[0, 3, 4, 1, 1, 0, 0, 0] 
[0, 3, 4, 1, 2, 1, 0, 0] 
[0, 3, 4, 1, 2, 2, 1, 0] 
[0, 3, 4, 1, 2, 2, 2, 1] 
[0, 3, 4, 4, 1, 0, 0, 0] 
[0, 3, 4, 4, 1, 1, 0, 0] 
[0, 3, 4, 4, 1, 2, 1, 0] 
[0, 3, 4, 4, 1, 2, 2, 1] 
[0, 3, 4, 4, 4, 1, 0, 0] 
[0, 3, 4, 4, 4, 1, 1, 0] 
[0, 3, 4, 4, 4, 1, 2, 1] 
[0, 3, 4, 4, 4, 4, 1, 0] 
[0, 3, 4, 4, 4, 4, 1, 1] 
[0, 0, 3, 1, 0, 0, 0, 0] 
[0, 0, 3, 1, 1, 0, 0, 0] 
[0, 0, 3, 1, 2, 1, 0, 0] 
[0, 0, 3, 1, 2, 2, 1, 0] 
[0, 0, 3, 1, 2, 2, 2, 1] 
[0, 0, 3, 4, 1, 0, 0, 0] 
[0, 0, 3, 4, 1, 1, 0, 0] 
[0, 0, 3, 4, 1, 2, 1, 0] 
[0, 0, 3, 4, 1, 2, 2, 1] 
[0, 0, 3, 4, 4, 1, 0, 0] 
[0, 0, 3, 4, 4, 1, 1, 0] 
[0, 0, 3, 4, 4, 1, 2, 1] 
[0, 0, 3, 4, 4, 4, 1, 0] 
[0, 0, 3, 4, 4, 4, 1, 1] 
[0, 0, 0, 3, 1, 0, 0, 0] 
[0, 0, 0, 3, 1, 1, 0, 0] 
[0, 0, 0, 3, 1, 2, 1, 0] 
[0, 0, 0, 3, 1, 2, 2, 1] 
[0, 0, 0, 3, 4, 1, 0, 0] 
[0, 0, 0, 3, 4, 1, 1, 0] 
[0, 0, 0, 3, 4, 1, 2, 1] 
[0, 0, 0, 3, 4, 4, 1, 0] 
[0, 0, 0, 3, 4, 4, 1, 1] 
[0, 0, 0, 0, 3, 1, 0, 0] 
[0, 0, 0, 0, 3, 1, 1, 0] 
[0, 0, 0, 0, 3, 1, 2, 1] 
[0, 0, 0, 0, 3, 4, 1, 0] 
[0, 0, 0, 0, 3, 4, 1, 1] 
[0, 0, 0, 0, 0, 3, 1, 0] 
[0, 0, 0, 0, 0, 3, 1, 1]

4개▼
[3, 1, 0, 0, 0, 0, 0, 0] 
[3, 1, 1, 0, 0, 0, 0, 0] 
[3, 1, 1, 1, 0, 0, 0, 0] 
[3, 1, 1, 2, 1, 0, 0, 0] 
[3, 1, 1, 2, 2, 1, 0, 0] 
[3, 1, 1, 2, 2, 2, 1, 0] 
[3, 1, 1, 2, 2, 2, 2, 1] 
[3, 4, 1, 0, 0, 0, 0, 0] 
[3, 4, 1, 1, 0, 0, 0, 0] 
[3, 4, 1, 1, 1, 0, 0, 0] 
[3, 4, 1, 1, 2, 1, 0, 0] 
[3, 4, 1, 1, 2, 2, 1, 0] 
[3, 4, 1, 1, 2, 2, 2, 1] 
[3, 4, 4, 1, 0, 0, 0, 0] 
[3, 4, 4, 1, 1, 0, 0, 0] 
[3, 4, 4, 1, 1, 1, 0, 0] 
[3, 4, 4, 1, 1, 2, 1, 0] 
[3, 4, 4, 1, 1, 2, 2, 1] 
[3, 4, 4, 4, 1, 0, 0, 0] 
[3, 4, 4, 4, 1, 1, 0, 0] 
[3, 4, 4, 4, 1, 1, 1, 0] 
[3, 4, 4, 4, 1, 1, 2, 1] 
[3, 4, 4, 4, 4, 1, 0, 0] 
[3, 4, 4, 4, 4, 1, 1, 0] 
[3, 4, 4, 4, 4, 1, 1, 1] 
[0, 3, 1, 0, 0, 0, 0, 0] 
[0, 3, 1, 1, 0, 0, 0, 0] 
[0, 3, 1, 1, 1, 0, 0, 0] 
[0, 3, 1, 1, 2, 1, 0, 0] 
[0, 3, 1, 1, 2, 2, 1, 0] 
[0, 3, 1, 1, 2, 2, 2, 1] 
[0, 3, 4, 1, 0, 0, 0, 0] 
[0, 3, 4, 1, 1, 0, 0, 0] 
[0, 3, 4, 1, 1, 1, 0, 0] 
[0, 3, 4, 1, 1, 2, 1, 0] 
[0, 3, 4, 1, 1, 2, 2, 1] 
[0, 3, 4, 4, 1, 0, 0, 0] 
[0, 3, 4, 4, 1, 1, 0, 0] 
[0, 3, 4, 4, 1, 1, 1, 0] 
[0, 3, 4, 4, 1, 1, 2, 1] 
[0, 3, 4, 4, 4, 1, 0, 0] 
[0, 3, 4, 4, 4, 1, 1, 0] 
[0, 3, 4, 4, 4, 1, 1, 1] 
[0, 0, 3, 1, 0, 0, 0, 0] 
[0, 0, 3, 1, 1, 0, 0, 0] 
[0, 0, 3, 1, 1, 1, 0, 0] 
[0, 0, 3, 1, 1, 2, 1, 0] 
[0, 0, 3, 1, 1, 2, 2, 1] 
[0, 0, 3, 4, 1, 0, 0, 0] 
[0, 0, 3, 4, 1, 1, 0, 0] 
[0, 0, 3, 4, 1, 1, 1, 0] 
[0, 0, 3, 4, 1, 1, 2, 1] 
[0, 0, 3, 4, 4, 1, 0, 0] 
[0, 0, 3, 4, 4, 1, 1, 0] 
[0, 0, 3, 4, 4, 1, 1, 1] 
[0, 0, 0, 3, 1, 0, 0, 0] 
[0, 0, 0, 3, 1, 1, 0, 0] 
[0, 0, 0, 3, 1, 1, 1, 0] 
[0, 0, 0, 3, 1, 1, 2, 1] 
[0, 0, 0, 3, 4, 1, 0, 0] 
[0, 0, 0, 3, 4, 1, 1, 0] 
[0, 0, 0, 3, 4, 1, 1, 1] 
[0, 0, 0, 0, 3, 1, 0, 0] 
[0, 0, 0, 0, 3, 1, 1, 0] 
[0, 0, 0, 0, 3, 1, 1, 1]

5개▼
[3, 1, 0, 0, 0, 0, 0, 0] 
[3, 1, 1, 0, 0, 0, 0, 0] 
[3, 1, 1, 1, 0, 0, 0, 0] 
[3, 1, 1, 1, 1, 0, 0, 0] 
[3, 1, 1, 1, 2, 1, 0, 0] 
[3, 1, 1, 1, 2, 2, 1, 0] 
[3, 1, 1, 1, 2, 2, 2, 1] 
[3, 4, 1, 0, 0, 0, 0, 0] 
[3, 4, 1, 1, 0, 0, 0, 0] 
[3, 4, 1, 1, 1, 0, 0, 0] 
[3, 4, 1, 1, 1, 1, 0, 0] 
[3, 4, 1, 1, 1, 2, 1, 0] 
[3, 4, 1, 1, 1, 2, 2, 1] 
[3, 4, 4, 1, 0, 0, 0, 0] 
[3, 4, 4, 1, 1, 0, 0, 0] 
[3, 4, 4, 1, 1, 1, 0, 0] 
[3, 4, 4, 1, 1, 1, 1, 0] 
[3, 4, 4, 1, 1, 1, 2, 1] 
[3, 4, 4, 4, 1, 0, 0, 0] 
[3, 4, 4, 4, 1, 1, 0, 0] 
[3, 4, 4, 4, 1, 1, 1, 0] 
[3, 4, 4, 4, 1, 1, 1, 1] 
[0, 3, 1, 0, 0, 0, 0, 0] 
[0, 3, 1, 1, 0, 0, 0, 0] 
[0, 3, 1, 1, 1, 0, 0, 0] 
[0, 3, 1, 1, 1, 1, 0, 0] 
[0, 3, 1, 1, 1, 2, 1, 0] 
[0, 3, 1, 1, 1, 2, 2, 1] 
[0, 3, 4, 1, 0, 0, 0, 0] 
[0, 3, 4, 1, 1, 0, 0, 0] 
[0, 3, 4, 1, 1, 1, 0, 0] 
[0, 3, 4, 1, 1, 1, 1, 0] 
[0, 3, 4, 1, 1, 1, 2, 1] 
[0, 3, 4, 4, 1, 0, 0, 0] 
[0, 3, 4, 4, 1, 1, 0, 0] 
[0, 3, 4, 4, 1, 1, 1, 0] 
[0, 3, 4, 4, 1, 1, 1, 1] 
[0, 0, 3, 1, 0, 0, 0, 0] 
[0, 0, 3, 1, 1, 0, 0, 0] 
[0, 0, 3, 1, 1, 1, 0, 0] 
[0, 0, 3, 1, 1, 1, 1, 0] 
[0, 0, 3, 1, 1, 1, 2, 1] 
[0, 0, 3, 4, 1, 0, 0, 0] 
[0, 0, 3, 4, 1, 1, 0, 0] 
[0, 0, 3, 4, 1, 1, 1, 0] 
[0, 0, 3, 4, 1, 1, 1, 1] 
[0, 0, 0, 3, 1, 0, 0, 0] 
[0, 0, 0, 3, 1, 1, 0, 0] 
[0, 0, 0, 3, 1, 1, 1, 0] 
[0, 0, 0, 3, 1, 1, 1, 1]

6개▼
[3, 1, 0, 0, 0, 0, 0, 0] 
[3, 1, 1, 0, 0, 0, 0, 0] 
[3, 1, 1, 1, 0, 0, 0, 0] 
[3, 1, 1, 1, 1, 0, 0, 0] 
[3, 1, 1, 1, 1, 1, 0, 0] 
[3, 1, 1, 1, 1, 2, 1, 0] 
[3, 1, 1, 1, 1, 2, 2, 1] 
[3, 4, 1, 0, 0, 0, 0, 0] 
[3, 4, 1, 1, 0, 0, 0, 0] 
[3, 4, 1, 1, 1, 0, 0, 0] 
[3, 4, 1, 1, 1, 1, 0, 0] 
[3, 4, 1, 1, 1, 1, 1, 0] 
[3, 4, 1, 1, 1, 1, 2, 1] 
[3, 4, 4, 1, 0, 0, 0, 0] 
[3, 4, 4, 1, 1, 0, 0, 0] 
[3, 4, 4, 1, 1, 1, 0, 0] 
[3, 4, 4, 1, 1, 1, 1, 0] 
[3, 4, 4, 1, 1, 1, 1, 1] 
[0, 3, 1, 0, 0, 0, 0, 0] 
[0, 3, 1, 1, 0, 0, 0, 0] 
[0, 3, 1, 1, 1, 0, 0, 0] 
[0, 3, 1, 1, 1, 1, 0, 0] 
[0, 3, 1, 1, 1, 1, 1, 0] 
[0, 3, 1, 1, 1, 1, 2, 1] 
[0, 3, 4, 1, 0, 0, 0, 0] 
[0, 3, 4, 1, 1, 0, 0, 0] 
[0, 3, 4, 1, 1, 1, 0, 0] 
[0, 3, 4, 1, 1, 1, 1, 0] 
[0, 3, 4, 1, 1, 1, 1, 1] 
[0, 0, 3, 1, 0, 0, 0, 0] 
[0, 0, 3, 1, 1, 0, 0, 0] 
[0, 0, 3, 1, 1, 1, 0, 0] 
[0, 0, 3, 1, 1, 1, 1, 0] 
[0, 0, 3, 1, 1, 1, 1, 1]

7개▼
[3, 1, 0, 0, 0, 0, 0, 0] 
[3, 1, 1, 0, 0, 0, 0, 0] 
[3, 1, 1, 1, 0, 0, 0, 0] 
[3, 1, 1, 1, 1, 0, 0, 0] 
[3, 1, 1, 1, 1, 1, 0, 0] 
[3, 1, 1, 1, 1, 1, 1, 0] 
[3, 1, 1, 1, 1, 1, 2, 1] 
[3, 4, 1, 0, 0, 0, 0, 0] 
[3, 4, 1, 1, 0, 0, 0, 0] 
[3, 4, 1, 1, 1, 0, 0, 0] 
[3, 4, 1, 1, 1, 1, 0, 0] 
[3, 4, 1, 1, 1, 1, 1, 0] 
[3, 4, 1, 1, 1, 1, 1, 1] 
[0, 3, 1, 0, 0, 0, 0, 0] 
[0, 3, 1, 1, 0, 0, 0, 0] 
[0, 3, 1, 1, 1, 0, 0, 0] 
[0, 3, 1, 1, 1, 1, 0, 0] 
[0, 3, 1, 1, 1, 1, 1, 0] 
[0, 3, 1, 1, 1, 1, 1, 1]

8개▼
[3, 1, 0, 0, 0, 0, 0, 0] 
[3, 1, 1, 0, 0, 0, 0, 0] 
[3, 1, 1, 1, 0, 0, 0, 0] 
[3, 1, 1, 1, 1, 0, 0, 0] 
[3, 1, 1, 1, 1, 1, 0, 0] 
[3, 1, 1, 1, 1, 1, 1, 0] 
[3, 1, 1, 1, 1, 1, 1, 1]

 

 

문제는 3개의 합인 경우이므로 더 짧아질 것.

PriorityQueue<Integer> que;
boolean[] primes;

public void primecal() {
	int max = que.peek();
	primes = new boolean[max];
	primes[0] = true;
	int calmax = (int)(Math.sqrt(max));
	for(int i=2;i<=calmax;i++) {
		for(int j=i*2;j<=max;j+=i) {
			primes[j-1] = true;
		}
	}
};

public void set(int[] nums, int[] check, int count, int sum) {
	if(count==3) {
		que.add(sum);
		return;
	} else {
		int start = -1;
		for(int i=0;i<check.length;i++) {
			if(check[i]==3) {
				start = i;
				break;
			}
		}
		
		for(int i=start+1;i<check.length;i++) {
			if(check[i]==0 && i>0 && check[i-1]>0) {
				if((count+1)+(check.length-1-i)<3) break;
				check[i] = 1;
				set(nums, check, count+1, sum+nums[i]);
				if(check[i]==1) check[i] = 2;
			}
		}
		
		boolean firstRemove = false;
		for(int i=start+1;i<check.length;i++) {
			if(!firstRemove && check[i]==1) {
				firstRemove = true;
				check[i] = 4;
			} else if(check[i]<3) check[i] = 0;
		}
	}
}

public int solution(int[] nums) {
	que = new PriorityQueue<>(Collections.reverseOrder());
	int[] check = new int[nums.length];
	for(int i=0;i<check.length-2;i++) {
		Arrays.fill(check, 0);
		check[i] = 3;
		set(nums, check, 1, nums[i]);
	}	
	primecal();
	int answer = 0;
	while(!que.isEmpty()) {
		int a = que.poll();
		if(!primes[a-1]) answer++;
	}
	return answer;
}

큐 초기화.

 

3가지가 가능한 칸의 시작점에 3으로 표시하면서 set 시작.

 

set에서는 3가지 조합에 대해 그 합을 큐에 저장. set이 진행되는 과정은 위에 첨부한 도표 참고.

 

set이 끝나면, 큐에 저장된 값 중 가장 큰 수로 소수 가늠 척도 생성(에라토스테네스의 체로 boolean[] 생성).

 

큐가 빌 때까지 값을 꺼내면서 소수인지 아닌지 확인하면서 answer++.

저작자표시 비영리 변경금지

'Problem Solving > programmers' 카테고리의 다른 글

[Lv3] 카카오프렌즈 컬러링북  (0) 2019.04.16
[Lv2] 점프와 순간이동  (1) 2019.04.15
[Lv2] 짝지어 제거하기  (0) 2019.04.15
[Lv2] N개의 최소공배수  (0) 2019.04.15
[Lv2] 최솟값 만들기  (0) 2019.04.15
'Problem Solving/programmers' Related Articles more
Comments

잘못된 정보가 있다면, 꼭 댓글로 알려주세요(비로그인 익명도 가능).

여러분의 피드백이 저와 방문자 모두를 올바른 정보로 인도할 수 있습니다.

감사합니다. -현록

후원해주실 분은 여기로→