프로그래머스 - 소수찾기 (레벨1, swift)

 

문제출처

programmers.co.kr/learn/courses/30/lessons/12921

 

문제설명

1부터 입력받은 숫자 n 사이에 있는 소수의 개수를 반환하는 함수, solution을 만들어 보세요. 

소수는 1과 자기 자신으로만 나누어지는 수를 의미합니다.
(1은 소수가 아닙니다.)

 

제한사항

    - n은 2이상 1000000이하의 자연수입니다.

 

입출력 예

n	result
10	4
5	3

 

입출력 예 설명

입출력 예 #1
1부터 10 사이의 소수는 [2,3,5,7] 4개가 존재하므로 4를 반환

입출력 예 #2
1부터 5 사이의 소수는 [2,3,5] 3개가 존재하므로 3를 반환

 

 

문제풀이

소요시간 : 20분 정도 소요

이 문제는 iOS수업 수강 당시 풀어본 적이 있어서 그때의 기억을 떠올리며 전체 코드는 일찍 짤 수 있었다.

그런데 막상 프로그래머스에서 채점을 해보면 자꾸 시간초과가 떠서 통과가 안되었다ㅠㅠ

이거 때문에 살짝 삽질을 했으나 질문하기를 보고 바로 해결할 수 있었다(아니였음 더 걸렸을듯ㅠㅠ)

 

질문하기를 살펴 보니까 시간 초과 뜨는 사람들이 나 말고도 많은 듯 했고 댓글을 보니 루트까지만 검사하면 된다는 말이 적혀 있었다.

그걸 보고 해당 부분을 루트+1로 바꿔주고 해당 숫자가 소수가 아닌 경우엔 끝까지 검사할 필요가 없어서 break를 추가해주니 바로 해결되었다!

이렇게만 써놓으면 무슨 말인지 잘 모르겠는데 아래 자세히 설명되어 있다.

이거 푸니까 +12점 되었는데😮 지금까지 중에서 제일 높은 점수를 받은듯???!!!! ㅋㅋ

 

먼저 소수의 의미가 무엇인지 파악하는 게 중요하다

소수란? 문제에도 나와있듯이 소수는 1과 자기 자신으로만 나누어지는 수를 의미한다.

따라서 10이 주어진다면 반복문을 통해 1부터 10까지 순차적으로 해당 숫자가 소수인지 체크하면 된다.

여기서 중요한 것은 반복문 안에서 해당 숫자가 소수인지 체크하는 부분인데,

보통 대부분 재귀함수를 이용해서 이를 구현하는 듯 하지만 난 2중 반복문을 사용했다.

 

짝수는 모두 2로 나누어지게 되고, 따라서 2를 제외한 짝수는 모두 소수가 아니다.

홀수는 소수(3, 5, 7, 11...)로 나누어 떨어지게 된다면 소수가 아니다(3 제외). 

이 때, 나누는 숫자는 나누어지는 숫자의 루트까지만 나누어 확인해 보면 된다.

예를 들어 9가 소수인지 확인하고 싶다면 9의 루트값인 3까지만 나누어 보면 되므로 2와 3만 나누어보면 된다.

그 이유는 아래를 살펴보자.

 

소수를 다시 표현해보면 1과 자기자신을 제외한 약수가 없는 수이다.

2는 1과 2외에 약수가 존재하지 않는다. 그러므로 소수이다.

9의 약수는 1, 3, 9로 1과 자기자신외에도 3이라는 약수가 존재하므로 소수가 아니다.

따라서 9가 소수인지 알고 싶다면 2부터 9까지의 숫자 중 나누어 떨어지는 수(여기서는 3)가 있는지 체크해 보고, 있다면 소수가 아니라고 판단하면 된다.

이때 2부터 9까지 모두 검사 할 필요는 없고 9의 루트 값인 3까지만 검사를 해보면 된다.

 

예를 들어 95가 소수인지 확인해 보도록 하자.

95의 약수는 1, 5, 19, 95이다. 이때 5까지만 확인하면 해당 수는 소수가 아니라는 것을 확인 할 수 있고 19까지 나눠 볼 필요가 없게 된다.

루트값 이후의 값으로 나누어 떨어지려면(이 경우 19) 반드시 해당 수의 몫이 루트값(약9.75) 이하에 존재(여기선 5가 있다)해야 한다.

 

다른 수를 예로 들어 보자. 

121의 약수는 1, 11, 121이다.

이 경우 11은 루트121에 해당한다. 1과 자기 자신을 제외한 약수가 존재할 수 있는 수 중 최대값이 바로 해당 수의 루트값이다.

따라서 루트값까지만 확인해 보면 된다!

 

이제 코드를 짜보자!!!

 

 1) 먼저 2부터 입력받은 숫자까지의 반복문을 구현하고,

 2) 그 안에 2부터 입력 받은 숫자의 루트까지 반복하여 해당 수가 나누어 떨어지는 지 확인하는 반복문을 구현한다.

 3) 만약 나누어 떨어진다면 해당 수는 소수가 아니라고 판별 하고 그 즉시 반복문 탈출(break)!

   -> 여기서 소수는 자기 자신을 제외하고 나누어 떨어지는 수이므로  " i != j " 를 통해 자기 자신으로 나누어 떨어지는 경우에는 소수로 체크될 수 있도록 한다

 4) 해당 수가 소수가 맞다면 count +1이 되도록 구현하고,

 5) 최종적으로 count를 return하면 끝!

 

위 순서대로 코드를 구현하면 아래와 같다.

 

 

푸는데 20분걸렸는데 포스트 작성하는데는 1시간 넘게 걸린 듯 하다ㅠㅠ