-
자바 반복문 isPrime 문제
아래는 전체 코드문이다.
package com.codestates.coplit; public class Solution { public boolean isPrime(int num) { if(num == 1) return false; //1은 당연히 false else if(num == 2) return true; //2는 true else if(num %2 == 0) return false; // 숫자가 2로 나뉘어 지는 짝수부터 일단 거름, return false int sqrt = (int)Math.sqrt(num); //소수가 아닌 숫자는 제곱근을 대칭으로 약수끼리 곱하면 원래 숫자가 나온다. //81을 예로 들면 약수는 1, 3, 9, 27, 81 인데 1*81 = 81, 3*27 = 81, 9*9 = 81 //이렇게 제곱근을 기준으로 대칭으로 약수를 곱하면 원래 숫자가 나오므로 굳이 제곱근 초과의 숫자는 나눌 필요가 없다는 소리이다. for(int i=3; i<=sqrt;i+=2) { //초깃값은 3으로 시작하고 제곱근까지 홀수만 반복 시킨다 if(num%i == 0) return false; } return true; } }
소수의 정의는 1과 자기 자신을 제외한 모든 숫자로 나누어도 나머지가 나오지 않는 숫자를 의미한다. 2,3,5,7,11,13.........
그렇다면 소수임을 판별하기 위해서는 자기 자신과 1을 제외한 그 사이의 수로 나누어 보면 그 숫자가 소수임을 판별할 수 있다.
public static void main(String[] args) {
int num = ??;
boolean prime = true;
for (int i = 2; i<num; i++) {
if( num%i == 0) {
prime = false;
break;
}
}
prime = false;
if(prime == true) {
System.out.println("소수입니다.");
}
else if(prime == false) {
System.out.println("소수가 아니다");
}
}이런 방식으로 무식하게 나누어 보는 방법도 가능하나
int 의 범위는 -2,147,483,648 ~ 2,147,483,647이다
만약 20억에 근접한 숫자가 소수인지를 판별하라 하면?
당신의 컴퓨터의 수명을 단축시키는데 기여를 하는 것이다.
풀이
먼저 숫자는 절대 2를 제외한 다른 숫자들은 소수가 될 수 없다.
그러므로 짝수는 용의선상에서 제외시킨다.
if(num%2 == 0) System.out.println("소수가 아닙니다.");두 번째로 우리는 그 숫자의 제곱근 까지만 나누어 보는 것으로 계산의 범위를 줄일 수 있다.
갑자기 제곱근이라 하니 놀랄 수 있는데
일단 예시를 들며 설명을 해보겠다
100의 약수는 1,2,4,5,10,20,25,50,100 이다.
10을 기준으로 대칭으로 숫자를 곱하면 1100 = 100, 250 = 100 ... 10*10 = 100으로 본래의 숫자가 나온다는 것을 알 수 있다.
이를 이용하면 무식하게 처음부터 끝까지 나누어 볼 필요 없이 제곱근 이내의 숫자로만 나누어 보면 소수인지 아닌지 판별 할 수 있다.
int sqrt = (int)(Math.sqrt(num));
for (int i = 3; i<sqrt; i+=2) {
if(num%i == 0) System.out.println("소수가 아님");
}그래서 총 합치면 이렇게 풀 수 있다
package com.codestates.coplit;
public class Solution {
public boolean isPrime(int num) {
if(num == 1) return false; //1은 당연히 false
else if(num == 2) return true; //2는 true
else if(num %2 == 0) return false; // 숫자가 2로 나뉘어 지는 짝수부터 일단 거름, return false
int sqrt = (int)Math.sqrt(num);
for(int i=3; i<=sqrt;i+=2) { //초깃값은 3으로 시작하고 제곱근까지 홀수만 반복 시킨다
if(num%i == 0) return false;
}
return true;
}
}hasRepeatedCharacter
-
아래는 전체 코드문이다
package com.codestates.coplit; public class Solution { public boolean hasRepeatedCharacter(String str) { // TODO: if(str.length() == 0) { return false; } //0123456789 //codestates //abcdefghijklmnopqrstuvwxyz for (int i = 0; i<str.length()-1;i++) { for(int j = i+1; j<str.length();j++){ if(str.charAt(i) == str.charAt(j)) return true; } } return false; } }문자열에 중복되는 글자기 있는지 true/false를 리턴하는 문제인데
이 문제도 상당히 골머리를 앓았다.
분명히 범위 설정이 잘 된 것 같았으나 abcdefghijklmnopqrstuvwxyz에서 false 가 아닌 true가 계속 나와 결국 해석을 듣고 풀 수 있게 되었다.
일단 문제를 풀기 위해서는 이중으로 for문이 필요하다
for (int i = 0; i<str.length()-1; i++){ for (int j = I+1; j<str.length();, i++) { ... } }여기서 왜 바깥의 반복문이 I<str.length() -1 이냐에 의문을 가질 수 있는데
codestates를 예시를 들면
i = 0부터 시작하므로 c부터 시작을 하고 마지막 문자 e 에서 끝날 거고, j는 i의 다음 문자부터 시작을 해서 가장 마지막 문자인 s까지 검사를 하게 된다.
즉 i = 0인 경우
C O D E S T A T E S ODESTATES를 검사를 하게 되고
i = 3인 경우
C O D E S T A T E S STATES부분을 검사하게 된다
그런데 여기서 i<str.length()로 설정을 하게 되면 마지막 문자인 S까지 검사하는 부분에 포함하게 되는데 S뒤에는 검사할 문자가 없으므로 -1을 붙여 설정을 한 것이다.
물론 i=1; i< str.length()로 설정하고 j=0; j<i로 설정해도 검사 순서만 바뀌게 되므로 둘 중 편한걸로 범위를 설정하면 된다.
for (int i = 1; i<str.length();i++) { for(int j = 0; j<i;j++){ if(str.charAt(i) == str.charAt(j)) return true; } } return false;이제 반복문 안에 str.charAt(i) == str.charAt(j) 이면 true를 반환하고 반복문 밖에는 false를 반환하게 하면 중복된 문자가 있을 때만 true를 반환하게 된다.
package com.codestates.coplit; public class Solution { public boolean hasRepeatedCharacter(String str) { // TODO: if(str.length() == 0) { return false; } for (int i = 0; i<str.length()-1;i++) { for(int j = i+1; j<str.length();j++){ if(str.charAt(i) == str.charAt(j)) return true; } } return false;
