[백준알고리즘-JAVA]1978번 풀이(소수 찾기) - 초보도 이해하는 풀이

안녕하세요

인포돈입니다.

백준 알고리즘 1978번 풀이입니다. 


* 참고사항
 - 개발환경은 eclipse을 기준으로 작성되었습니다.
 - java언어를 이용하여 문제를 풀이합니다.
 - 알고리즘 문제는 풀이를 보고 해답을 찾는 것도 중요하지만 무엇보다 스스로 풀이를 시도해봐야 합니다!!
(해당 풀이를 보기 전 충분히 문제에 대해 고민해봐야 합니다!)
 - 해당 풀이 말고도 수많은 풀이 방법이 존재합니다.

 

---

백준 1978 (소수 찾기)

 

문제

주어진 수 N개 중에서 소수가 몇 개인지 찾아서 출력하는 프로그램을 작성하시오.

입력

첫 줄에 수의 개수 N이 주어진다. N은 100 이하이다. 다음으로 N개의 수가 주어지는데 수는 1,000 이하의 자연수이다.

출력

주어진 수들 중 소수의 개수를 출력한다.

입력 예시

4
1 3 5 7

출력 예시

3

성공코드

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

public class Main {
	public static void main(String args[]) throws IOException{
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		
		int num = Integer.parseInt(br.readLine());
		String[] str = br.readLine().split(" ");
		int s = 0;
		int cnt = 0;
		
		for(int i = 0 ; i < str.length ; i++) {
			
			if(Integer.parseInt(str[i]) !=1) {
			for(int j = 2 ; j <= (int)Math.sqrt(Integer.parseInt(str[i])); j++)
			{
				if(Integer.parseInt(str[i])%j == 0) {
					s +=1;
					break;
				}
			}
			if(s == 0) cnt +=1;
			s = 0;
			}
		}
		
		System.out.println(cnt);
		}
		}

알고리즘의 풀이를 좀 더 정형하 하기 위해서 앞으로 문제에 필요한 기준을 STEP으로 나누어 하나하나 이해해 나갈 수 있게 풀이해 보겠습니다 ~!

 

기본적이 형식은 흐름도 / 문제 STEP 풀이 / 느낀 점 및 알게 된 점 이렇게 차근차근 알려드리겠습니다.!

 

---

알고리즘 흐름도

입력받기 받기 -> 받은 입력 값 중에 소수 값 찾기 -> 소수 값을 찾을 때마다 COUNT 해주기 -> COUNT 출력하기

 

이러한 흐름으로 진행해 보겠습니다.

 

 

---

STEP1 소수에 대한 이해

해당 문제를 알기 위해서는 먼저 소수에 대해서 알아야 합니다.

 

소수 : 자기 자신과 1로만 나누어지는 수를 의미한다.

 

여기서 예외는 1 1일 자기 자신과 1로 나누어지지만 소수로 취급하지 않는다.

 

이에 따라 소수는 2 3 5 7 11 13... 이런 식으로 나오게 됩니다.

 

---

STEP2 소수 값 찾기

소수 값은 어떻게 찾아야 할까요? 이문제가 바로 이문제의 핵심이라고 볼 수 있습니다.

 

알고리즘 수학 문제는 기본적으로 코딩의 기술보다는 수학적인 식을 도출하는 것이 더욱 중요해 보입니다.

 

수학이 싫더라도 이번만큼은..... ㅎㅎ 수학을 조금 이해하셔야 합니다.

 

일단 소수를 쭉 나열해 보죠

 

2  3  5  7  11  13  17  19  23  29  31  37  41  43  47  53  59  61  67  71  73......

 

보통의 수학 관련 알고리즘은 해당 숫자들을 나열해놓고 직관적으로 보이게 해 논 다음 패턴을 찾는 것이 가장 기본적인 방법입니다.

 

그러나 이번에는 제눈에도 해당 패턴이 잘 보이지 않았습니다.

 

그래서 참고한 것이 바로 수학에서 소수 찾기를 참고해 봤습니다.

 

 - 어떤 자연수 N이 소수임을 판정하기 위해선 Root(N)까지의 수 중 1을 제외하고 그 자연수의 약수가 있는지 확인하면 된다.

(그냥 이런 공식이 생각이 안 나면 다른 알고리즘을 참고하지 말고, 수학적 의미를 파악해서 코딩을 해보는 게 좋습니다.)

 

라는 소수 찾기 방식을 알아볼 수 있었습니다.

 

그렇다면, 1을 예외로 처리한 뒤 2부터 반복문을 돌려서 찾으면 되지 않을까? 하는 생각이 들어서 바로 실행에 옮겨봤습니다.

 

for(int i = 0 ; i < str.length ; i++) {
			if(Integer.parseInt(str[i]) !=1) {
			for(int j = 2 ; j <= (int)Math.sqrt(Integer.parseInt(str[i])); j++)
			{
				if(Integer.parseInt(str[i])%j == 0) {
				}
			}
			}
		}

여기서 str을 이전에 받은 입력을 공백으로 분리하여 저장한 String배열입니다.

 

for문을 통해 str인덱스를 하나씩 검사를 하게 되죠

 

if문을 통해 만약 그 인덱스에 있는 숫자가 1이 아니면 또 다른 for문을 이용하라고 되어있죠.

 

for문을 통해 이제 저희가 바로 찾을 수를 2부터 해당 인덱스에 나누어봅니다.

 

 - 처음에 2로 나누어서 나머지가 0 이면, 2로 나누기가 된다는 의미 => 즉, 소수가 될 수 없게 되죠.

 - 처음 2로 나누어 떨어지지 않을 시 다음 for문으로 3을 나누어 떨어지게 합니다. 이런 식으로 만약에 root(N)까지 반복문을 돌았는데도 하나도 나누어 떨어지지 않으면 그 값이 바로 소수 값이 되게 됩니다.

 

---

STEP 3 찾은 소수 값 표현해보기

for(int i = 0 ; i < str.length ; i++) {
			
			if(Integer.parseInt(str[i]) !=1) {
			for(int j = 2 ; j <= (int)Math.sqrt(Integer.parseInt(str[i])); j++)
			{
				if(Integer.parseInt(str[i])%j == 0) {
					s +=1;
					break;
				}
			}
			if(s == 0) cnt +=1;
			s = 0;
			}
		}

자 변수가 몇 개가 추가되었는데 하나하나 알려드릴게요

 

int s => 해당 변수는 쉽게 생각하면 2로 나누어지면 s에 1을 더해라 => 이 말은 즉, s가 양수가 되면 소수 값이 아니다!

int cnt => 해당 변수는 소수 값이 있으면 +1을 해주어 실질적으로 우리가 찾으려는 값!!

 

내부에 있는 j for문을 다 돌고 나면 str의 인덱스 하나의 소수 판별이 끝나게 됩니다. 끝나게 되었을 때 s가 0이면(즉, 나누어 떨어지는 값이 없을 경우), cnt에 1을 더해서 소수가 1개 있다는 것을 알리게 되죠

 

맨 아래 s를 0으로 초기화한 것은 인덱스 0 번째에서 조사한 s값이 다음 인덱스 1번에 영향을 주지 않기 위해서 반복문을 돌릴 때마다 초기화가 되도록 설정해 줬습니다!

 

---

 

해당 STEP을 다 따라오셨다면, 이제 cnt변수를 출력만 해주면 해당 알고리즘 문제도 쉽게 해결이 가능하게 되죠!!