최대 자연수 값 n이 주어질 때 [1,n]에서 소수가 몇 개 있는지 출력하는 문제이다. 필자의 경우 첫번째 시도를 시간초과로 틀렸다. 그래서 질문하기를 보니 에라토테네스의 체(어떤 사람을 이걸 에라이체라고 하더라)를 활용하면 풀 수 있다고 했다. 이용했더니 한번에 풀림! 에라토테네스의 체는 큰 수가 소수가 맞는지 아닌지에 대한 판별을 할 때 유용하다고 한다. 간단히 설명을 하자면 25가 소수인지 알고 싶을 때, 2~24까지 전부 나눠보는 것이 아니라 그의 제곱근인 5를 2~5로 나눠보면 된다는 것이다. 왜 제곱근까지 나눠보면 되냐면 우리가 어떠한 수를 나눌 때 몫이 생긴다. 이 몫이 그 수의 제곱근이하이기 때문이라고 한다(더 자세히 알고 싶은 사람은 검색해보자.). 아무튼 이 원리를 이용하고 효율성 검사까지 모두 통과하였다.
publicclassPrimeNum{ publicstaticvoidmain(String[] args) { int n = 10; int answer = 0; boolean add = true; for(int i = 2; i <= n; i++) { add = true; for(int j = 2; j <= Math.sqrt(i); j++) { if(i%j==0) { add = false; break; } } if(add) answer++; } } }
1은 소수가 아니므로 2부터 n까지 i가 소수인지 검토하는 프로그램을 짰다. 원래 두번째 for문에서 i-1까지 나눠보는 걸로 하였는데, 에라토테네스의 체로 제곱근까지 나눠본다. 이때 등호를 넣어준 이유는 제곱근이 자연수로 딱 떨어지는 경우가 있기 때문이다. 가령 4가 소수인지 판별하기 위해선 2까지 해당하는 약수가 있는지 봐야한다. 소수판별은 위와 같이 가능하다. 소수 판별을 한다는 것을 저장하기 위해 add라는 플래그를 세워두었다. 만약 약수가 하나라도 존재하면 add는 false가 되어 answer++문을 넘어간다. 총 시간복잡도는 \(O(n\sqrt{n})\)이다.
publicstaticvoidmain(String[] args) { String s = "a234"; boolean answer = false; if(s.length() == 4 || s.length() == 6) { answer = true; for(int i = 0; i < s.length(); i++) { char c = s.charAt(i); int ascii = (int)c; if(c > 57 || c < 48) answer = false; } } } }
첫번째로 문자열의 길이가 4또는 6을 만족하는지 확인한다. 길이를 만족하면 true로 답을 바꾼다. 그 다음 조건으로 모든 문자열의 문자가 숫자인지 아스키코드로 확인한다. 만약 만족하지 않는 문자가 존재한다면 answer를 false로 바꾼다. 총 시간복잡도는 \(O(n)\)이다.
테스트
다른 사람의 풀이를 보니 NumberFormatException을 활용하여 문제를 푼 사람이 있었다. 문자열을 int로 파싱하는데 에러가 나면 answer를 false로 바꾸는 것이다.
배열이 주어졌을 때, 중복을 제거한 배열을 반환하는 문제이다. 단, 배열의 순서는 유지되어야 한다.
문제풀이
디큐를 활용하여 문제를 풀자 디큐는 스택과 큐의 성질을 동시에 가지고 있는 자료구조이다. 그렇다면 이 문제는 스택과 큐의 성질을 둘다 이용하고 싶기 때문에 이용했다고 보면된다. 중복을 제거하는 방법은 조금만 생각해보면 쉽게 알 수 있다. 바로 그 전 숫자와 같은지 같지 않은지 확인하면 된다. 그러면 스택으로만 풀 수 있다고 반문하는 사람이 있겠지만 이 역시 아니다 스택을 활용할 경우 중복은 제거할 수 있지만, 순서를 유지할 수 없다. 스택은 LIFO이기 때문이다. 그래서 큐의 성질이 FIFO가 필요하고 이것이 디큐를 사용한 이유이다. 물론 스택을 굳이 사용하겠다면 방법은 있다. 스택을 통해 중복을 제거한뒤 배열에 거꾸로 담거나, 역전을 시켜주거나 방법은 많다. 여러 방법으로 이 문제를 풀어보고 시간복잡도도 함께 계산해보면 좋은 공부가 될 수 있을 것이다.
