[프로그래머스] Level 1. 소수 찾기

안녕하세요!

오늘은 소수 찾기 문제를 풀어보겠습니다 :D

---

문제

 

 

풀이

저는 isPrime 함수를 만들어 풀어보았습니다!

소수 구하는 방법은 소수 찾기 Feat. 에라토스테네스의 체 글을 참고해주세요!ㅎㅎ

isPrime 함수를 이용해서 Bool 값이 true 일때 count 값을 +1 해줍니다.

그 후에 n = 2 일때는 1을 출력해야하므로 삼항 연산자를 이용해 해당 연산이 true일때 (n = 2) 1을 출력하고, false일때는 count 값을 출력하도록 했습니다!

 

 

func solution(_ n:Int) -> Int {
    var primes:[Bool] = [Bool](repeating:false, count:n+1);
    var count = 0;
    for i in 2...n {
        if(!primes[i]){
            count = count + 1;
        }
        for j in 1...(n/i) {
            primes[i*j]=true;
        }
    }
    return count;
}

이 풀이 방법도 저랑 비슷한데, 저는 함수를 만들었지만 init(repeating:count:) 를 사용하였네요?

bool 값으로 구성되어있는 Primes 배열을 만들어줍니다. 

repeating : 반복할 문자, 숫자, 부울 등을 넣어줌
count : 반복 횟수

 

for i in 2...n {
	if(!primes[i]){
		count = count + 1;
	}
	for j in 1...(n/i) {
		primes[i*j]=true;
	}
}

 

내부에 있는 For 문부터 보겠습니다! 이 부분이 이해가 어려워서 애먹었어요ㅠㅠ

n = 5 라고 가정했을 때, 총 n + 1 = 6 개의 false로 구성된 배열이 생깁니다.

제가 이해하기 쉬우려고 그린 그림인데 혹시 도움이 될까해서 첨부했어요!

처음 if 문이 돌면서 count = 1이 됩니다.

그 후, 내부 for문이 돌면서 i * j 에 해당하는 위치의 값을 true로 바꾸어줍니다. n / i 번 돌면 종료가 되고

다시 위로 올라가 if 문이 돌면서 false가 true로 바뀌었으면 count +1이 됩니다.

이와 같은 작업을 반복하면 소수가 count 됩니다. 

 

여기서 저는 true로 한 번 바뀐 게 다시 true로 되면 False가 되는건가? 했는데

그건 아니더라구요!ㅎㅎ,,,,

 

혹시 몰라서 코드로 찍어본 것도 첨부하겠습니다!

 

 

---

 

정확성 테스트

내가 푼 풀이

다른 풀이

프로그래머스에 있는 다른 코드를 가져와서 돌려봤는데, 다른 풀이는 효율성 테스트2에서 실패하네요??

아무래도 너무 복잡해서 그런것 같아요.. 배열 값도 계속 바꾸고 For문도 2중이고 if문도 들어가있으니까!??

소수 관련 문제가 꽤 많은 것 같기도하고 넘 어려워서 따로 글로 정리했어요! 

저랑 비슷하게 어려움 느끼셨던 분은 소수 찾기 Feat. 에라토스테네스의 체 글을 참고하면 좋을 것 같습니다 :D