[백준] 1978번 : 소수 찾기- Java(자바)

오랜만에 글을 쓰게됐네요. 이번주는 국비에서 홈페이지를 만들라고 해서 따로 자바를 올리지 못 했습니다. 조원끼리 만드는거라 시간이 좀 걸리는거 같습니다. 다음주 발표인데 아마 일요일쯤이면 프로그래밍은 끝날거 같습니다. 다음주부터는 또 당분간 알고리즘 문제를 올리도록 하겠습니다.

이번 문제는 소수 개수를 카운팅하는 문제였습니다. 별 어려움 없는 문제였습니다.

Step 0. 해답 코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;
public class Search_Sosu {

	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		int N = Integer.parseInt(br.readLine());
		StringTokenizer st = new StringTokenizer(br.readLine(), " ");
		int count = 0;
		 x : for (int i = 0; i < N; i++) { //N회만큼 반복
			int a = Integer.parseInt(st.nextToken()); //소수 확인할 a값들
			if (a == 1) { //1은 소수가 아님
				continue;
			}
			for (int j = 2; j < a; j++) { //2~a-1까지의 수랑 a랑 나눠서 나머지가 0이면 소수가 아니므로 for문 스킵.
				if (a % j == 0) {
					continue x;
				} 
			}
			count++; //모든 a-1까지 나눠서 전부 나머지가 존재했다면 소수이므로 count++
		}
		System.out.println(count);
	}

}

Step 1. 문제 접근

N개의 수들은 자연수이므로 우선 1인 경우는 제외해줍니다. 그 후 입력된 숫자 a를 갖고 2~a-1까지를 a와 나눠서 나머지가 0이 된다면 그 수는 소수가 아닌것이라고 판단했습니다.

Step 2. 문제 해결

1. 테스트 횟수 N과 소수인지를 찾을 숫자들을 StringTokenizer를 이용해서 변수st에 넣어줬습니다. 또한 count = 0으로 둬서 소수의 개수를 구했습니다.

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

2. 첫 for문을 이용해서 N만큼 반복되게 하였고 라벨 값으로 x를 선언해줬습니다. a값에는 st에 저장했던 소수인지를 판별할 수들을 하나씩 nextToken()메서드를 사용하여 불러왔습니다. 만약 a가 1이라면 소수가 아니므로 continue를 사용하여 다음 수를 찾도록 하였습니다.(제 식에서는 1이 들어가면 count가 추가되기 때문에 따로 조건을 줬습니다.)

x : for (int i = 0; i < N; i++) { //N회만큼 반복
	int a = Integer.parseInt(st.nextToken()); //소수 확인할 a값들
	if (a == 1) { //1은 소수가 아님
		continue;
	}

3. 각 수 a를 2부터 a-1까지의 수와(a가 5라면 2,3,4와..) 나눠서 나머지가 0이라면 소수가 아니므로 위의 라벨값을 사용하여 다음 수를 확인하였습니다. 그리고 해당식을 전부 통과할 경우 count++을 해주어 소수의 개수를 늘려줬습니다.

for (int j = 2; j < a; j++) { //2~a-1까지의 수랑 a랑 나눠서 나머지가 0이면 소수가 아니므로 for문 스킵.
	if (a % j == 0) {
		continue x;
	} 
}
	count++; //모든 a-1까지 나눠서 전부 나머지가 존재했다면 소수이므로 count++
}
System.out.println(count);
}

Step 3. 느낀 점

이번 문제는 쉬어는가는 느낌의 문제였던거 같습니다. 그래도 자만하지 않고 열심히 풀어야할거 같습니다. 무엇보다 알고리즘 푸는게 재밌어서 좋은거 같습니다!

출처 : 백준 1978번 https://www.acmicpc.net/problem/1978