프로그래머스 - 소수 찾기

문제 설명

 int 타입 변수 n으로부터 입력받은 값을 가지고 1부터 n사이에 있는 자연수 사이에서 소수의 개수를 찾는 문제이다. 코드를 보며 설명하도록 하겠다. 

solution

 우선 코드를 살펴보기 전 소수에 대해서 이야기를 하자면 소수는 자기 자신을 나누어 떨어지게 하는 숫자가 1과 자기 자신을 제외하고 존재하지 않는다면 그 숫자를 소수라고 한다. 이를 확인하기 위해 for 중첩 반복문을 사용하였다. i % j가 0이라면 나누어 떨어지는 것이기 때문에 반복을 통해 나누어 떨어지지 않는 수를 찾았다. 저 코드에서 만약 6, 9, 13번째 줄의 코드들이 존재하지 않는다면 이 코드에 문법적인 오류는 없지만 제대로 된 값을 반환받지는 못한다. 그 이유는 8번 줄의 if 조건문으로 인해 1과 자기 자신(i)을 제외한 사이의 숫자들 중 i를 나누어 떨어지게 하는 숫자들이 존재하면 내부의 for 반복문을 빠져나와 다음 i를 실행하는 것은 맞지만 내부의 for 반복문을 빠져나오고 나서 14번째 줄의 코드를 만나게 되면 우리가 원하지 않는 숫자를 걸러내기 8번에서 break문으로 내부의 for 반복문에서 빠져나왔다 해도 아무런 조건이 존재하지 않기 때문에 answer(소수가 몇 개인지 세어주는 변수)를 1 증가시킨다. 즉, 반복을 매번 진행할 때마다 answer++는 실행이 된다는 것이다. 이렇게 되면 올바르게 소수의 개수를 확인할 수 없기 때문에 bool 타입 변수를 넣어 8번째 줄의 조건문이 참이라면 flag에 false를 대입하고 break로 내부의 반복문을 빠져나와 13번째 줄의 조건문이 거짓이기 때문에 소수의 개수를 증가시키지 않게 된다. 이렇게 solution은 끝이 난다. 하지만 이 코드는 시간 복잡도가 정말 안 좋은 코드이다. 사실 나도 몰랐다 코드를 작성하고 직접 돌려보기 전까지는,, 그래서 다른 코드들을 찾아보다 새로 알게 된 것이 있었다. 오늘은 그 코드를 소개해보려 한다.

에라토스테네스의 체

 이 코드의 원리를 간략하게 설명하기 위해서 소수의 정의에 대해 다시 한번 생각해보면 소수는 자기 자신보다 작은 값들 중 1을 제외하고는 아무런 숫자도 자기 자신을 나누어 떨어지게 하지 못하는 숫자를 소수라고 했다. 그렇다면 이 세상에 존재하는 모든 수는 소수들의 배수인 셈이다. 이런 점을 이용하여 2의 배수 3의 배수 4의 배수 5의 배수... n의 배수를 걸러내면 소수들만이 남게 된다. 하지만 여기서 4는 이미 2의 배수이기 때문에 4의 배수를 따로 고려할 필요가 없게 된다. 이해가 잘 되지 않는다면 코드를 보면서 자세하게 설명해보도록 하겠다.

 우선, 큰 흐름을 이야기하면 배열을 생성하여 배열의 각 인덱스에 해당 인덱스 번호의 값을 저장하고 2의 배수 3의 배수... n의 배수들은 0으로 다시 초기화를 한다. 그러고 나서 for 반복문을 사용해 배열 arr에 저장돼있는 값들 중 0이 아닌 값들의 개수를 세면 그것이 소수의 개수가 된다. 5 ~ 7번째 줄의 코드들은 바로 위의 설명으로 충분한 설명이 됐을 거라고 생각한다. 이제 8 ~ 14번째 줄의 코드들을 보면, 이 코드들이 n의 배수 값들을 제외(0으로 초기화)시키는 과정이다. 중첩 for문을 사용했고 범위는 두 for문 모두 2부터로 설정해주었는데 이유는 배열의 0, 1번 인덱스의 요소의 값은 0과 1이기 때문에 볼 필요가 없기 때문이다. 마지막으로 배열에 저장된 값들을 for 반복문으로 한 번 돌면서 0이 아닌 값(배수가 아닌 값)이면 'answer++'를 실행하여 최종 answer 값을 반환한다.