https://app.codility.com/programmers/lessons/11-sieve_of_eratosthenes/count_non_divisible/
문제
- 배열 A가 주어지며, N개의 정수들로 이루어져 있다.
- 배열 A의 각 원소들에서 나누어지지 않는 수들의 개수를 구하라.
- 예시 : A[0] = 3 A[1] = 1 A[2] = 2 A[3] = 3 A[4] = 6
- A[0] = 3, the non-divisors are: 2, 6,
- A[1] = 1, the non-divisors are: 3, 2, 3, 6,
- A[2] = 2, the non-divisors are: 3, 3, 6,
- A[3] = 3, the non-divisors are: 2, 6,
- A[4] = 6, there aren't any non-divisors.
return [2, 4, 3, 2, 0]
제한조건
- N is an integer within the range [1..50,000];
- each element of array A is an integer within the range [1..2 * N].
N은 1 ~ 50,000 사이의 정수이다.( 빈 배열이 없다 )
A배열의 각 원소들은 1 ~ 2*N 사이의 정수이다.
풀이
- N이 1개일 경우에는 나눌 수가 없으므로 return [0]
- int[] table 배열을 만든다( table에는 count한 수를 저장 )
- copyA( A배열을 복사 )를 sort 시킨 후 for문으로 뒤쪽부터 순회한다.
- 자신보다 큰 수는 나눌 수 없는 수임으로 배제하고 그 아래 수들만 비교하여 나눌수 없는 수를 카운트한다.
- 그 아래 수들을 비교할 때, 같은 수를 만나면 break
- table에 수가 있는지 확인하고, 수가 없을 경우 갱신한다.
결과
time out 에러...
소스코드( 1트 )
// you can also use imports, for example:
import java.util.*;
// you can write to stdout for debugging purposes, e.g.
// System.out.println("this is a debug message");
class Solution {
public int[] solution(int[] A) {
// write your code in Java SE 8
int N = A.length;
int[] answer = new int[N];
// 0. 예외처리
if( N < 2 ){
answer[0] = 0;
return answer;
}
// 1. A배열을 복사
int[] copyA = Arrays.copyOfRange(A, 0, A.length);
Arrays.sort(copyA);
int[] table = new int[2*N + 1];
int overNum = 0;
int sameNum = 0;
int prev = 2 * N + 1;
for( int i=N-1; i>=0; i-- ){
if( prev == copyA[i] ){
sameNum += 1;
}else{
sameNum = 0;
}
int nonNum = 0;
// 아래에 있는 수만 파악
for( int j=0; j<i; j++ ){
// System.out.println("copyA[i] : " + copyA[i] + " / copyA[j] : " + copyA[j]);
if( copyA[i] == copyA[j] ) break;
if( copyA[i] % copyA[j] != 0 ){
nonNum += 1;
}
}
// System.out.println("nonNum : " + nonNum + " / overNum : " + overNum + " / sameNum : " + sameNum);
table[copyA[i]] = nonNum + overNum - sameNum;
overNum += 1;
prev = copyA[i];
}
for( int i=0; i<N; i++ ){
answer[i] = table[A[i]];
}
return answer;
}
}
소스코드( 2트 )
- table에 저장된 수는 고려하지 않는 걸 추가함( 결국 같은 수는 같은 nondivisible을 갖게 됨으로 )
// you can also use imports, for example:
import java.util.*;
// you can write to stdout for debugging purposes, e.g.
// System.out.println("this is a debug message");
class Solution {
public int[] solution(int[] A) {
// write your code in Java SE 8
int N = A.length;
int[] answer = new int[N];
// 0. 예외처리
if( N < 2 ){
answer[0] = 0;
return answer;
}
// 1. A배열을 복사
int[] copyA = Arrays.copyOfRange(A, 0, A.length);
Arrays.sort(copyA);
int[] table = new int[2*N + 1];
int overNum = 0;
int sameNum = 0;
int prev = 2 * N + 1;
for( int i=N-1; i>=0; i-- ){
if( table[copyA[i]] != 0 ) {
overNum += 1;
continue;
}
if( prev == copyA[i] ){
sameNum += 1;
}else{
sameNum = 0;
}
int nonNum = 0;
// 아래에 있는 수만 파악
for( int j=0; j<i; j++ ){
if( copyA[i] == copyA[j] ) break;
if( copyA[i] % copyA[j] != 0 ){
nonNum += 1;
}
}
table[copyA[i]] = nonNum + overNum - sameNum;
overNum += 1;
prev = copyA[i];
}
for( int i=0; i<N; i++ ){
answer[i] = table[A[i]];
}
return answer;
}
}
0.6xx였는데 조금 빨라짐..ㅠ
결국 구글링..
http://chienchikao.blogspot.com/2017/10/codility-lesson-11-sieve-of_21.html
https://sustainable-dev.tistory.com/31
3번째 블로그를 보니 이해함.. A배열 안에서 약수의 개수를 구하는게 핵심이였던 문제...( 그 이전에 약수의 개수를 구하는 것을 기억해야하는데... 바보다ㅠ )
구글링 후 3트...
- 약수의 개수를 구하고 전체 배열의 개수를 카운트 한 것과 연계하여 풀이
// you can also use imports, for example:
import java.util.*;
// you can write to stdout for debugging purposes, e.g.
// System.out.println("this is a debug message");
class Solution {
public int[] solution(int[] A) {
// write your code in Java SE 8
int N = A.length;
int[] answer = new int[N];
if( N < 2 ){
answer[0] = 0;
return answer;
}
// 1. A배열의 수들이 몇개 있는지 카운트할 배열 생성
int[] table = new int[2*N + 1]; // 제한조건에 의해서 2*N + 1가 됨
// 2. A배열의 수 카운트
for( int i=0; i<N; i++ ){
table[A[i]] += 1;
}
// 3. 약수의 개수 세기
for( int i=0; i<N; i++ ){ // 배열 개수만큼 반복
int divider = 0;
// System.out.println("i : " + i );
for( int j=1; j*j<=A[i]; j++ ){
if( A[i] % j == 0 ){
divider += table[j]; // 배열 A가 가지고 있는 원소 개수 만큼 더해줌
// System.out.println("divider : " + divider);
if( A[i] / j != j ){ // j와 같을 경우에는 같은 수가 됨으로 제외
System.out.println("divider : " + divider);
divider += table[ A[i]/j ];
}
}
}
// System.out.println("divider : " + divider);
answer[i] = N - divider;
}
return answer;
}
}