[백준] 1644: 소수의 연속합 - JS(투포인터)

  목 차

• 문제
• 접근 방식
• 풀이

 

---

  문제

 

 

단, 20은 0인데, 20은 소수가 아니기 때문에 0이 나와야 한다.

 

 

  접근 방식

 

2~N까지의 소수를 모두 구해야 하기 때문에 이전에 '소수 구하기'에서 구현했던 코드를 가져와 M부터 N 이였던 것을 처음부터 N 까지로 변경했다.

 

그리고 이 문제를 읽으면서 두 포인터 기법을 사용해야 겠다고 생각했다. 

먼저 소수를 배열에 넣는다. 그리고 start와 end가 있는데 먼저 가장 첫 번째 요소를 가리키게 해 준다. 만약 N과 같거나 작다면 end를 하나 올려준다. start와 end가 1 이상 차이 나게 되면 그 요소들을 더해준다. 그리고 똑같이 N과 같거나 작다면 end를 하나 올려주고, N 보다 크다면 start를 하나 올려주어 결과적으로 맨 앞에 있는 요소를 빼는 역할을 하게 해 준다.

 

큰 틀은 위와 같이 해주면 된다. 이제 디테일을 잡아야 하는데

디테일 포인트들은 다음과 같다.

 

• start와 end는 소수배열의 length 미만이어야 한다.
• end 가 start 보다 작다면 end를 start와 같게 만들어 준다.
• start와 end는 처음 시작지점이 같아야 한다.
• 제출할 때 require 해서 가져온 입력은 꼭 parseInt를 해주자. 

 

처음 설계는 다음과 같이했다.

 

 

  풀이

 

 

{
	const N = 53;
  
  const data: boolean[] = new Array(N+1).fill(false);
	data[0] = true;
	data[1] = true;

	const minority: number[] = [];

  for(let i = 2; i <= Math.sqrt(N); i++){
		if(data[i] == true){continue};
		
		let j = i;
		while(j <= N){
			j = j + i;
			if(j > N){break};
			data[j] = true;
		};
  }

	for(let [index, value] of data.entries()){
		if(index <= N){
			if(!value){
				minority.push(index);
			}
		}
	}
  
	let result = 0;

	let startPointer = 0;
	let endPointer = 0;


	while(startPointer < minority.length && endPointer < minority.length){
		let added = 0;

		for(let i = startPointer; i <= endPointer; i++){
			added += minority[i];
		};

		if(added == N) {result++};

		if(added <= N){
			endPointer++; 
		} else {
			startPointer++
			if(endPointer < startPointer){
				endPointer = startPointer;
			};
		};

	}
	console.log(result);
	
}