[데알] 백준 알고리즘 No. 1978 소수 찾기(Java)

 

■ 문제 링크

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

1978번: 소수 찾기

 

■ 소스코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;

public class Main {

	public static void main(String[] args) throws IOException {

		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st;
		
		int N = Integer.parseInt(br.readLine());
		int[] arr = new int[N];
		int answer=0;
		
		st = new StringTokenizer(br.readLine(), " ");

		for(int i=0;i<N;i++) {
			
			arr[i]=Integer.parseInt(st.nextToken());
		}
		
		for(int i=0;i<arr.length;i++) {
			int cnt = 0;
			if(arr[i]==1) {
				continue;
			} else {

				for(int j=2;j<arr[i];j++) {
					if(arr[i]%j==0) {
						continue;
					} else {
						cnt++;
					}
				}
				
				if(cnt==(arr[i]-2)) {
					answer++;
				}
			}
		}
		System.out.println(answer);
	}
}

 

 

■ 풀이

 

---

소수(Prime Number)는 1과 해당 숫자를 제외한 약수는 가지지 않는다.

---

이 문제에서 눈여겨볼 부분은 continue였다. 

for문이 중첩되어있고 그 안에 모두 if-else가 있기때문에 break를 사용하려한다면 주의해야한다.

아직 값 비교가 끝나지 않았는데 반복문이 멈춰버리는 상황이 발생할 수 있기 때문....!

기능과 사용할 위치를 잘 파악해야한다.

 

로직은 심플 오브 심플!

1) 첫째줄에 입력받은 숫자만큼의 길이를 가진 배열을 생성하고 둘째줄에서 입력받은 숫자들을 StringTokenizer를 사용해 공백을 기준으로 나눠서 배열에 저장한다. 

 

2) 배열만큼 반복하는 loop을 만들고 배열의 요소들을 체크하기 시작한다.

 

3-1) 요소의 값이 1이라면,

continue; 1은 소수에 해당되지 않으므로 넘어간다.

3-2) 요소 값이 1이 아니라면,

다시 반복문을 선언해서 (시작값을 2로 하고) 요소의 값 % j 의 나머지값을 체크해서 0이라면, 요소의 값이 j로 나누어떨어진 것을 의미하므로 더이상 반복할 필요가 없는 요소이므로 continue를 해준다.

3-3) 요소의 값 % j 의 나머지값을 체크해서 0이 아니라면, cnt를 증가시켜준다. 

3-4) 한 요소의 약수 찾기가 끝나면 cnt를 체크해서 요소의 값 - 2 한 값과 같다면 나누어떨어지는 수가 한 번도 등장하지 않았음을 의미하므로 소수가 된다. (소수의 개수를 담을 answer를 1증가시키고 2)로 돌아간다.)

2)부터 배열에 있는 모든 요소들을 inner loop의 j값과 %연산으로 나머지를 확인하면서 소수인지 아닌지 확인하고 

 

4) 최종적으로 answer를 출력하면 입력받은 숫자 중 소수의 개수를 출력할 수 있다. 

 

■ 후기

 

 

중첩된 반복문이 있어서 시간이 많이 나올 줄 알았는데 생각보다 오래걸리진 않은듯...!

다른 풀이 보니 boolean타입 변수, 배열 대신 ArrayList사용한 경우도 있었다. 어떤게 효율이 더 높을지는 다시 테스트해보는 걸로!!

 

 

 

 

 

잘못된 점이나 보충할 부분이 있으면 코멘트 남겨주세요

작은 조언이 저에겐 성장의 원동력이 됩니다 :-)