기본 콘텐츠로 건너뛰기

코딩 테스트 - 소수 찾기



이 문제는 Kotlin으로 정답 체크 할 수 없어서 그냥 IDE에서 짜 보았습니다.

package programmers;

class 소수_찾기_Java_230728 {
/*
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를 반환
*/
public int solution(int n) {
boolean[] isPrime = new boolean[n + 1];
int count = 0;

// 모든 수를 소수로 가정하고 초기화
for (int i = 2; i <= n; i++) {
isPrime[i] = true;
}

// 에라토스테네스의 체 알고리즘
// 에라토스테네스의 체 알고리즘은 2부터 시작하여 배수들을 지워가면서 소수를 찾는 방법
for (int i = 2; i * i <= n; i++) {
if (isPrime[i]) {
for (int j = i * i; j <= n; j += i) {
isPrime[j] = false;
}
}
}

// 소수 개수 세기
for (int i = 2; i <= n; i++) {
if (isPrime[i]) {
count++;
}
}

return count;
}


public int solution_최적화(int n) {
//주어진 n 이하의 소수를 찾는데, 이때 n이 최대 1,000,000 이하의 자연수라는 조건이 있으므로, 약간의 최적화를 추가
if (n < 2) {
return 0; // 1보다 작거나 같은 수는 소수가 없음
}

boolean[] isPrime = new boolean[n + 1];
int count = 0;

// 모든 수를 소수로 가정하고 초기화
for (int i = 2; i <= n; i++) {
isPrime[i] = true;
}

// 최적화 1: n의 제곱근까지만 반복
int sqrtN = (int) Math.sqrt(n);
for (int i = 2; i <= sqrtN; i++) {
if (isPrime[i]) {
for (int j = i * i; j <= n; j += i) {
isPrime[j] = false;
}
}
}

// 소수 개수 세기
for (int i = 2; i <= n; i++) {
if (isPrime[i]) {
count++;
}
}

return count;
}
/*
이 최적화에서 sqrtN n의 제곱근을 나타냅니다.
에라토스테네스의 체 알고리즘에서, n보다 큰 수 중 소수가 존재한다면
그 소수는 n의 제곱근보다 큰 수로 나타날 수 없습니다.
따라서 반복문을 i <= sqrtN까지만 돌리면 충분하며,
이렇게 하면 시간 복잡도가 줄어들어 좀 더 최적화된 소수 찾기 메소드가 됩니다.
*/

}

package programmers

class 소수_찾기_Kotlin_230728 {
// BooleanArray Kotlin에서 배열을 생성하는 방법이며, for 루프의 구문이 조금 다를 수 있습니다.
// 또한, Kotlin에서는 while 루프를 사용하는 것도 가능하므로, for 루프를 while 루프로 변경한 부분도 있습니다.

fun solution(n: Int): Int {
val isPrime = BooleanArray(n + 1)
var count = 0

// 모든 수를 소수로 가정하고 초기화
for (i in 2..n) {
isPrime[i] = true
}

// 에라토스테네스의 체 알고리즘
for (i in 2..n) {
if (isPrime[i]) {
var j = i * i
while (j <= n) {
isPrime[j] = false
j += i
}
}
}

// 소수 개수 세기
for (i in 2..n) {
if (isPrime[i]) {
count++
}
}

return count
}

fun solution_최적화(n: Int): Int {
// 주어진 n 이하의 소수를 찾는데, 이때 n이 최대 1,000,000 이하의 자연수라는 조건이 있으므로, 약간의 최적화를 추가
if (n < 2) {
return 0 // 1보다 작거나 같은 수는 소수가 없음
}

val isPrime = BooleanArray(n + 1)
var count = 0

// 모든 수를 소수로 가정하고 초기화
for (i in 2..n) {
isPrime[i] = true
}

// 최적화 1: n의 제곱근까지만 반복
val sqrtN = Math.sqrt(n.toDouble()).toInt()
for (i in 2..sqrtN) {
if (isPrime[i]) {
var j = i * i
while (j <= n) {
isPrime[j] = false
j += i
}
}
}

// 소수 개수 세기
for (i in 2..n) {
if (isPrime[i]) {
count++
}
}

return count
}
}


댓글

이 블로그의 인기 게시물

Ebook - 전자책 drm 상관 없이 pdf로 만들기

yes24와 교보문고에서 ebook을 구매 해야 했는데 너무 불편하고, 필기가 매우 화날 정도로 안 좋아서 원시적으로 사용하기로 했다. 1. 목적 : ebook에서 필기 및 사용이 불편하여 pdf로 변환  2. 용도 : 개인 사용 목적이며 화질이 다소 저하되어도 필기만 용이하면 상관 없음 3. 방법 1) 휴대폰 및 카메라로 동영상을 촬영했다. DRM 때문에 프로그램으로는 촬영이 안 되는 것을 확인했다. 2) 마우스 클릭 해주는 매크로를 사용했다. (1) key_macro.exe > https://blog.daum.net/pg365/250 듀얼 모니터에서 위치 이탈 현상이 있긴 해도 괜찮았다. (2) AutoClick.exe > http://bestsoftwarecenter.blogspot.com/2011/02/autoclick-22.html 이 걸로 잘 사용했다. 3초마다 한 번 클릭하도록 사용했다. 3) 동영상을 이미지로 변경해주는 프로그램을 사용했다. Free Video to JPG Converter > https://free-video-to-jpg-converter.kr.uptodown.com/windows 일 하면서 듀얼 모니터에 켜 놨는데 속도가 괜찮았다. * Every frame 으로 사용해야 한다. 4) 중복 사진 제거해주는 프로그램을 사용했다. VlsiPics  > http://www.visipics.info/index.php?title=Main_Page 생각보다 느리니 퇴근시에 걸어놓고 가면 된다. 한번 play가 끝나면 Auto-select 하고 Delete 하면 된다. 5) 이미지를 일괄 Crop 작업 해주는 프로그램을 사용했다. JPEGCrops > https://jpegcrops.softonic.kr/ * https://joker1209.tistory.com/11 도 참고했다. View -> Large 로 크게 본 뒤, Edit -> Syncronize Crops 로 일괄 동일하게 적용하는 방식을 사

개발 공부 - json JSONObject 사용 시 백슬래시(\), 원화 표시(\) 제거 및 치환

import org.json.simple.JSONObject; String dataString = new String(authData.toJSONString()); dataString = dataString.replaceAll("\\\\", ""); String 으로 안 바뀌는 가 싶어서 String 으로 변환 해 주고 작업 하였다. 사실 toJSONString 해도 정상 동작 해야 하는데 이유를 잘 모르겠음. 그리고 나서 다시 이클립스 구동 하니 toString 도 먹은 걸로 봐서 이상하다고 생각! String dataString = authData.toString(); dataString = dataString.replaceAll("\\\\", ""); 어쨌든 백 슬래시 제거를 해줘야 하는데 \\ 도 아니고 \\\\를 해야 변환이 가능했다는 결말이었습니다. 참고 : https://stackoverflow.com/questions/15450519/why-does-string-replace-not-work/15450539 test =test.replace("KP", "");  replace 후에 담아 주지 않으면 적용이 안 됩니다!

카카오 계정 삭제 - 카카오 계정 탈퇴 하는 법

몇일 동안 카카오톡 계정 삭제를 하려고 신경질이 나 있었습니다. 간단하게 말하면 그냥 https://accounts.kakao.com/weblogin/deactivate 이 링크만 알려줬으면 될 걸 왜 이렇게 어렵게 만들어!! 안녕하세요. kakao입니다. 문의해주신 내용 관련하여 답변 드리겠습니다. 카카오톡을 이용해 주셔서 감사합니다. 카카오에서는 고객님의 카카오계정을 임의로 탈퇴 처리 해드리기어려운 점 양해 부탁드리며,  번거로우시더라도 탈퇴를 원하시는 카카오계정으로 로그인 하시어  아래의 방법을 통해 직접 탈퇴 하실 수 있습니다. 카카오계정은 카카오톡을 포함하여 카카오스토리, 카카오게임, 카카오페이지 등  다른 카카오 서비스를 모두 이용할 수 있는 통합 계정입니다.  따라서, 카카오톡을 탈퇴하여도 카카오계정에 연결된 다른 서비스가 있다면  카카오계정은 자동으로 탈퇴되지 않습니다.  카카오톡, 카카오스토리 서비스를 이용하고 계신 경우  카카오계정에 연결된 카카오 서비스를 모두 탈퇴하신 후  마지막으로 카카오스토리, 카카오톡을 탈퇴하시면 카카오계정이 함께 탈퇴됩니다.    ※ 카카오계정에 연결된 서비스는      ' 카카오톡, 카카오스토리 앱> 더보기> 내 프로필> 카카오계정> 연결된 서비스 관리' 에서       확인하실 수 있습니다.  ※ 카카오톡, 카카오스토리 탈퇴 시에 '카카오계정은 탈퇴되지 않는다'는 안내를 받으셨다면     카카오톡, 카카오스토리 탈퇴한 이후에 카카오계정 탈퇴 페이지에서     별도로 카카오계정 탈퇴를 진행하시면 됩니다. 단, 카카오계정 탈퇴 시 금전적인 문제가 발생할 수 있거나,  타인의 서비스 이용에 영향을 줄 수 있는 경우에는 바로 탈퇴할 수 없으며,  해당 서비스를 해지하거나 설정을 변경하신 후 카카오계정을 탈퇴하실 수 있습니다.  ※ 이미 카카