백준 9421 소수상근수, 에라토스테네스의체 swift 풀이

 

 

 

---

백준 9421 소수상근수 문제설명

오늘은 백준 9421번, 소수상근수를 풀어보겠습니다. 소수상근수 난이도는 solved.ac기준 실버1입니다. 

 

 

 

 

시간제한은 1초, 메모리제한은 256MB입니다. 

 

 

 

 

본 문제의 요지는 상근수이자, 소수인 소수상근수를 출력하는 문제입니다. 상근수, 소수에 대한 사항은 위의 설명을 참고하시기 바랍니다. 

 

 

 

 

N이 입력되면, N보다 같거나 작은 모든 소수상근수를 오름차순으로 개행단위 출력하면 됩니다. 2 ~ N까지의 숫자 중 소수 중에서 상근수인 소수상근수를 구할때마다 출력하도록 할ㄹ 예정입니다. 

 

여기서 눈여겨보셔야할 부분은 N의 범위입니다. N의 범이가 100만이므로, O(N^2)과 같은 시간복잡도로는 시간초과가 발생합니다. 저는 특정 범위 내의 모든 소수를 구할 수 있는 에라토스테네스의 체를 사용할 예정입니다.

에라토스테네스의 체 시간 복잡도는 NloglogN입니다.

 

 

 

---

백준 9421 소수상근수 swift 문제풀이
swift 문자열 입력처리

위의 코드는 이런식으로 입력을 받을 수 있다는 것을 알려드리기 위해 올렸습니다. Int(readLine()!)!으로 정수를 받아도 되지만, 위와 같이 입력 최적화를 할 수 있다는 점만 참고하시면 됩니다. 해당 문제는 정수 하나만 받으므로, 위와 같이 입력최적화를 할 필요가 없을 수도 있지만말이죠.

 

아래 코드부터 제대로 입력을 받겠습니다.

 

 

 

N 정수를 받습니다. prime은 N+1의 크기를 갖고 각각의 인덱스는 해당 인덱스 값이 소수인지를 확인하는 지표가 되도록 할 예정입니다. 

answer는 출력해야할 소수상근수를 누적할 예정입니다. prime의 0, 1 인덱스에는 미리 false값을 넣어 소수가 아님을 표시해두었습니다.

 

이제 에라토스테네스의체를 활용해서 소수를 기록해보겠습니다.

 

 

---

에라토스테네스의체 활용하기
prime 배열, defer 활용

소수는 2부터 시작하므로 바깥 for문 인덱스를 2로 시작하여 에라토스테네스의체를 구현합니다. idx * idx <= N은 idx <= sqrt(Double(N)) 과 같은 효과를 얻지만, 소수를 구하는 로직은 정수만 사용되므로, sqrt를 사용하는 것은 권장되지 않습니다. 

 

17행을 보시면 defer 문법이 있는데요. 선언된 블록이 종료될때 실행하고자 하는 코드를 넣어두면 코드를 보다 간결하게 사용할 수 있습니다. 제가 예전 defer에 대해 포스팅한 링크가 아래에 있으니 참고하시기 바랍니다. 

iOS swift 문법 팁, defer문 특징 및 사용방법

에라토스테네스의 체를 통해 위와 같이 소수가 아닌 인덱스의 값을 false로 변경하면서 소수 인덱스의 값만 true가 남게 됩니다. 에라토스테네스의 체를 사용하면 특정 범위의 모든 소수를 빠른시간에 구할 수 있다는 장점이 있어, 특정 범위의 모든 소수를 구하고자 할때 유용하게 사용할 수 있습니다. 에라토스테네스의체에 대해서는 관심있으시다면 별도로 찾아보시기 바랍니다.

 

 

---

소수상근수 구하기

소수를 모두 구했담면 이제 소수상근수를 구하는 로직을 구현할 단계입니다. 3부터 시작해서 4, 5, 6.... N까지 차례대로 소수상근수 여부를 체크합니다. 

28행) 이 코드에서도 defer 문을 통해 블록 종료 시 num += 1을 실행하도록 정의하고 있습니다. 

29행) 현재의 num이 소수인지를 체크합니다. 소수가 아니면 num += 1을 하고 다음 숫자를 보면 되겠죠.

31행) 소수상근수의 값 변환 중의 값 중복이 발생하는지를 체크하는데 사용하는 dictionary, dic입니다.

32행) while true로 소수상근수 여부가 확정될때까지 무한루프를 실행합니다. isSK는 소수상근수인지 여부를 기록합니다. 

34 ~ 39행) 소수상근수인지를 확인하기 위해 현재 숫자의 각자리수의 제곱을 더해주는 과정입니다. 

41 ~ 44행) 만약 위와 같은 제곱 합 연산 후에 1이 되면 상근수이므로 isSK = true 설정 후 반복문을 빠져나갑니다. 반대로, 소수상근수 체크 연산을 반복하는데, 중복된 값이 발생하는 소수상근수가 아니므로, isSK = false를 유지한 채로 while문을 빠져나갑니다.

 

47 ~ 49행) 이제 소수상근수 였는지를 확인하고 소수상근수였다면 answer문자열에 누적시킵니다. 개행단위 출력을 해야하므로, "\n"도 문자열 상태에 따라 추가해줍니다.

 

이렇게 에라토스테네스의체를 활용해서 swift언어로 소수상근수 문제를 풀 수 있었습니다. 이제 남은 것은 소수상근수를 모아둔 문자열, answer를 출력하는 일입니다. 

 

 

 

 

이렇게 백준 9421번, 소수상근수를 풀 수 있었습니다. 본 코드의 제출결과는 아래와 같습니다. 

 

 

 

 

백준 9421번, 소수상근수 에라토스테네스의체 활용 swift문제풀이 제출결과