Tasks Details
The submission is being evaluated.
The submission is being evaluated.
The submission is being evaluated.
The submission is being evaluated.
The submission is being evaluated.
The submission is being evaluated.
The submission is being evaluated.
The submission is being evaluated.
The submission is being evaluated.
The submission is being evaluated.
medium
Compute the number of intersections in a sequence of discs.
Task Score
93%
Correctness
87%
Performance
100%
We draw N discs on a plane. The discs are numbered from 0 to N − 1. An array A of N non-negative integers, specifying the radiuses of the discs, is given. The J-th disc is drawn with its center at (J, 0) and radius A[J].
We say that the J-th disc and K-th disc intersect if J ≠ K and the J-th and K-th discs have at least one common point (assuming that the discs contain their borders).
The figure below shows discs drawn for N = 6 and A as follows:
A[0] = 1 A[1] = 5 A[2] = 2 A[3] = 1 A[4] = 4 A[5] = 0
There are eleven (unordered) pairs of discs that intersect, namely:
- discs 1 and 4 intersect, and both intersect with all the other discs;
- disc 2 also intersects with discs 0 and 3.
Write a function:
class Solution { public int solution(int[] A); }
that, given an array A describing N discs as explained above, returns the number of (unordered) pairs of intersecting discs. The function should return −1 if the number of intersecting pairs exceeds 10,000,000.
Given array A shown above, the function should return 11, as explained above.
Write an efficient algorithm for the following assumptions:
- N is an integer within the range [0..100,000];
- each element of array A is an integer within the range [0..2,147,483,647].
Copyright 2009–2025 by Codility Limited. All Rights Reserved. Unauthorized copying, publication or disclosure prohibited.
Solution
Programming language used Java 21
Time spent on task 3 minutes
Notes
not defined yet
Code: 09:05:25 UTC,
c,
verify,
result: Failed
1234567891011121314151617181920212223242526272829303132333435363738394041424344454647484950515253545556575859606162636465666768
// you can also use imports, for example:
import java.util.*;
// you can use System.out.println for debugging purposes, e.g.
// System.out.println("this is a debug message");
class Solution {
int MAX = 10000000;
public int solution(int[] A) {
// write your code in Java SE 8
/*
문제 :
디스크의 원점과 반지름 길이가 주어진다.
각 디스크가 겹치는 개수를 출력하라
방법 :
1. 각 디스크의 최대점과 최저점을 각각 배열로 가지고 있는다.
2. 최대점 배열과 최저점 배열을 정렬 한다.
(정렬을 하면 최대점 배열은 원점의 위치를 고려한 낮은 값부터 높은 값 으로 정렬 되고
최저점 배열은 원점의 위치를 고려한 폭이 정렬된다.)
--> 반복
3. 최대점 배열의 처음의 값보다 최저점 배열의 값이 클때까지의 개수를 구한다.
(이 개수는 최대점 배열의 처음 값을 포함하는 디스크의 개수다)
4. 전체 값을 구할때 교차점 개수 + 최소점 개수 - 최대점 개수 - 1을한다.
(최대점과 -1을 빼는 이유는 중복값을 제거하기 위함이다.)
** 만약 10,000,000개의 넘는 교차점이 존재하면 -1을 출력한다.
5. 교차점의 개수를 출력한다.
*/
int length = A.length;
int[] upper_disc = new int[length];
int[] lower_disc = new int[length];
// 최대점 배열과 최저점 배열에 최대점,최저점을 구한다. 문제에 따라 식은 index가 원점,이 되고 index에 해당하는 값이 반지름이다.
for(int i=0; i < length; i++){
upper_disc[i] = i + A[i]; // 최대점 = 원점 + 반지름
lower_disc[i] = i - A[i]; // 최저점 = 원점 - 반지름
}
// 최대점과 최저점 배열을 정렬한다.
Arrays.sort(upper_disc);
Arrays.sort(lower_disc);
int lower_index = 0;
int upper_index = 0;
int intersection = 0;
// 교차점의 개수를 구한다. 기준은 최대점 배열이며 최대점보다 최저점이 작은 경우 최대점이 최저점에 포함된다.
for(upper_index=0; upper_index < length; upper_index++){
// 하나의 디스크와 겹쳐지는 다른 디스크의 개수를 구한다.
while(lower_index < length && upper_disc[upper_index] >= lower_disc[lower_index]){
lower_index++;
}
// 교차점에서 중복값을 제거하기 위해 upper_index-1을 한다.
intersection = intersection + lower_index - upper_index -1;
}
if(intersection < MAX)
intersection = -1;
return intersection;
}
}
Code: 09:05:37 UTC,
java,
verify,
result: Failed
1234567891011121314151617181920212223242526272829303132333435363738394041424344454647484950515253545556575859606162636465666768
// you can also use imports, for example:
import java.util.*;
// you can use System.out.println for debugging purposes, e.g.
// System.out.println("this is a debug message");
class Solution {
int MAX = 10000000;
public int solution(int[] A) {
// write your code in Java SE 8
/*
문제 :
디스크의 원점과 반지름 길이가 주어진다.
각 디스크가 겹치는 개수를 출력하라
방법 :
1. 각 디스크의 최대점과 최저점을 각각 배열로 가지고 있는다.
2. 최대점 배열과 최저점 배열을 정렬 한다.
(정렬을 하면 최대점 배열은 원점의 위치를 고려한 낮은 값부터 높은 값 으로 정렬 되고
최저점 배열은 원점의 위치를 고려한 폭이 정렬된다.)
--> 반복
3. 최대점 배열의 처음의 값보다 최저점 배열의 값이 클때까지의 개수를 구한다.
(이 개수는 최대점 배열의 처음 값을 포함하는 디스크의 개수다)
4. 전체 값을 구할때 교차점 개수 + 최소점 개수 - 최대점 개수 - 1을한다.
(최대점과 -1을 빼는 이유는 중복값을 제거하기 위함이다.)
** 만약 10,000,000개의 넘는 교차점이 존재하면 -1을 출력한다.
5. 교차점의 개수를 출력한다.
*/
int length = A.length;
int[] upper_disc = new int[length];
int[] lower_disc = new int[length];
// 최대점 배열과 최저점 배열에 최대점,최저점을 구한다. 문제에 따라 식은 index가 원점,이 되고 index에 해당하는 값이 반지름이다.
for(int i=0; i < length; i++){
upper_disc[i] = i + A[i]; // 최대점 = 원점 + 반지름
lower_disc[i] = i - A[i]; // 최저점 = 원점 - 반지름
}
// 최대점과 최저점 배열을 정렬한다.
Arrays.sort(upper_disc);
Arrays.sort(lower_disc);
int lower_index = 0;
int upper_index = 0;
int intersection = 0;
// 교차점의 개수를 구한다. 기준은 최대점 배열이며 최대점보다 최저점이 작은 경우 최대점이 최저점에 포함된다.
for(upper_index=0; upper_index < length; upper_index++){
// 하나의 디스크와 겹쳐지는 다른 디스크의 개수를 구한다.
while(lower_index < length && upper_disc[upper_index] >= lower_disc[lower_index]){
lower_index++;
}
// 교차점에서 중복값을 제거하기 위해 upper_index-1을 한다.
intersection = intersection + lower_index - upper_index -1;
}
if(intersection < MAX)
intersection = -1;
return intersection;
}
}
Code: 09:05:54 UTC,
java,
verify,
result: Passed
1234567891011121314151617181920212223242526272829303132333435363738394041424344454647484950515253545556575859606162636465666768
// you can also use imports, for example:
import java.util.*;
// you can use System.out.println for debugging purposes, e.g.
// System.out.println("this is a debug message");
class Solution {
int MAX = 10000000;
public int solution(int[] A) {
// write your code in Java SE 8
/*
문제 :
디스크의 원점과 반지름 길이가 주어진다.
각 디스크가 겹치는 개수를 출력하라
방법 :
1. 각 디스크의 최대점과 최저점을 각각 배열로 가지고 있는다.
2. 최대점 배열과 최저점 배열을 정렬 한다.
(정렬을 하면 최대점 배열은 원점의 위치를 고려한 낮은 값부터 높은 값 으로 정렬 되고
최저점 배열은 원점의 위치를 고려한 폭이 정렬된다.)
--> 반복
3. 최대점 배열의 처음의 값보다 최저점 배열의 값이 클때까지의 개수를 구한다.
(이 개수는 최대점 배열의 처음 값을 포함하는 디스크의 개수다)
4. 전체 값을 구할때 교차점 개수 + 최소점 개수 - 최대점 개수 - 1을한다.
(최대점과 -1을 빼는 이유는 중복값을 제거하기 위함이다.)
** 만약 10,000,000개의 넘는 교차점이 존재하면 -1을 출력한다.
5. 교차점의 개수를 출력한다.
*/
int length = A.length;
int[] upper_disc = new int[length];
int[] lower_disc = new int[length];
// 최대점 배열과 최저점 배열에 최대점,최저점을 구한다. 문제에 따라 식은 index가 원점,이 되고 index에 해당하는 값이 반지름이다.
for(int i=0; i < length; i++){
upper_disc[i] = i + A[i]; // 최대점 = 원점 + 반지름
lower_disc[i] = i - A[i]; // 최저점 = 원점 - 반지름
}
// 최대점과 최저점 배열을 정렬한다.
Arrays.sort(upper_disc);
Arrays.sort(lower_disc);
int lower_index = 0;
int upper_index = 0;
int intersection = 0;
// 교차점의 개수를 구한다. 기준은 최대점 배열이며 최대점보다 최저점이 작은 경우 최대점이 최저점에 포함된다.
for(upper_index=0; upper_index < length; upper_index++){
// 하나의 디스크와 겹쳐지는 다른 디스크의 개수를 구한다.
while(lower_index < length && upper_disc[upper_index] >= lower_disc[lower_index]){
lower_index++;
}
// 교차점에서 중복값을 제거하기 위해 upper_index-1을 한다.
intersection = intersection + lower_index - upper_index -1;
}
if(intersection > MAX)
intersection = -1;
return intersection;
}
}
Code: 09:06:03 UTC,
java,
verify,
result: Passed
1234567891011121314151617181920212223242526272829303132333435363738394041424344454647484950515253545556575859606162636465666768
// you can also use imports, for example:
import java.util.*;
// you can use System.out.println for debugging purposes, e.g.
// System.out.println("this is a debug message");
class Solution {
int MAX = 10000000;
public int solution(int[] A) {
// write your code in Java SE 8
/*
문제 :
디스크의 원점과 반지름 길이가 주어진다.
각 디스크가 겹치는 개수를 출력하라
방법 :
1. 각 디스크의 최대점과 최저점을 각각 배열로 가지고 있는다.
2. 최대점 배열과 최저점 배열을 정렬 한다.
(정렬을 하면 최대점 배열은 원점의 위치를 고려한 낮은 값부터 높은 값 으로 정렬 되고
최저점 배열은 원점의 위치를 고려한 폭이 정렬된다.)
--> 반복
3. 최대점 배열의 처음의 값보다 최저점 배열의 값이 클때까지의 개수를 구한다.
(이 개수는 최대점 배열의 처음 값을 포함하는 디스크의 개수다)
4. 전체 값을 구할때 교차점 개수 + 최소점 개수 - 최대점 개수 - 1을한다.
(최대점과 -1을 빼는 이유는 중복값을 제거하기 위함이다.)
** 만약 10,000,000개의 넘는 교차점이 존재하면 -1을 출력한다.
5. 교차점의 개수를 출력한다.
*/
int length = A.length;
int[] upper_disc = new int[length];
int[] lower_disc = new int[length];
// 최대점 배열과 최저점 배열에 최대점,최저점을 구한다. 문제에 따라 식은 index가 원점,이 되고 index에 해당하는 값이 반지름이다.
for(int i=0; i < length; i++){
upper_disc[i] = i + A[i]; // 최대점 = 원점 + 반지름
lower_disc[i] = i - A[i]; // 최저점 = 원점 - 반지름
}
// 최대점과 최저점 배열을 정렬한다.
Arrays.sort(upper_disc);
Arrays.sort(lower_disc);
int lower_index = 0;
int upper_index = 0;
int intersection = 0;
// 교차점의 개수를 구한다. 기준은 최대점 배열이며 최대점보다 최저점이 작은 경우 최대점이 최저점에 포함된다.
for(upper_index=0; upper_index < length; upper_index++){
// 하나의 디스크와 겹쳐지는 다른 디스크의 개수를 구한다.
while(lower_index < length && upper_disc[upper_index] >= lower_disc[lower_index]){
lower_index++;
}
// 교차점에서 중복값을 제거하기 위해 upper_index-1을 한다.
intersection = intersection + lower_index - upper_index -1;
}
if(intersection > MAX)
intersection = -1;
return intersection;
}
}
Code: 09:06:12 UTC,
java,
final,
score:
93
1234567891011121314151617181920212223242526272829303132333435363738394041424344454647484950515253545556575859606162636465666768
// you can also use imports, for example:
import java.util.*;
// you can use System.out.println for debugging purposes, e.g.
// System.out.println("this is a debug message");
class Solution {
int MAX = 10000000;
public int solution(int[] A) {
// write your code in Java SE 8
/*
문제 :
디스크의 원점과 반지름 길이가 주어진다.
각 디스크가 겹치는 개수를 출력하라
방법 :
1. 각 디스크의 최대점과 최저점을 각각 배열로 가지고 있는다.
2. 최대점 배열과 최저점 배열을 정렬 한다.
(정렬을 하면 최대점 배열은 원점의 위치를 고려한 낮은 값부터 높은 값 으로 정렬 되고
최저점 배열은 원점의 위치를 고려한 폭이 정렬된다.)
--> 반복
3. 최대점 배열의 처음의 값보다 최저점 배열의 값이 클때까지의 개수를 구한다.
(이 개수는 최대점 배열의 처음 값을 포함하는 디스크의 개수다)
4. 전체 값을 구할때 교차점 개수 + 최소점 개수 - 최대점 개수 - 1을한다.
(최대점과 -1을 빼는 이유는 중복값을 제거하기 위함이다.)
** 만약 10,000,000개의 넘는 교차점이 존재하면 -1을 출력한다.
5. 교차점의 개수를 출력한다.
*/
int length = A.length;
int[] upper_disc = new int[length];
int[] lower_disc = new int[length];
// 최대점 배열과 최저점 배열에 최대점,최저점을 구한다. 문제에 따라 식은 index가 원점,이 되고 index에 해당하는 값이 반지름이다.
for(int i=0; i < length; i++){
upper_disc[i] = i + A[i]; // 최대점 = 원점 + 반지름
lower_disc[i] = i - A[i]; // 최저점 = 원점 - 반지름
}
// 최대점과 최저점 배열을 정렬한다.
Arrays.sort(upper_disc);
Arrays.sort(lower_disc);
int lower_index = 0;
int upper_index = 0;
int intersection = 0;
// 교차점의 개수를 구한다. 기준은 최대점 배열이며 최대점보다 최저점이 작은 경우 최대점이 최저점에 포함된다.
for(upper_index=0; upper_index < length; upper_index++){
// 하나의 디스크와 겹쳐지는 다른 디스크의 개수를 구한다.
while(lower_index < length && upper_disc[upper_index] >= lower_disc[lower_index]){
lower_index++;
}
// 교차점에서 중복값을 제거하기 위해 upper_index-1을 한다.
intersection = intersection + lower_index - upper_index -1;
}
if(intersection > MAX)
intersection = -1;
return intersection;
}
}
Code: 09:05:25 UTC,
c,
verify,
result: Failed
1234567891011121314151617181920212223242526272829303132333435363738394041424344454647484950515253545556575859606162636465666768
// you can also use imports, for example:
import java.util.*;
// you can use System.out.println for debugging purposes, e.g.
// System.out.println("this is a debug message");
class Solution {
int MAX = 10000000;
public int solution(int[] A) {
// write your code in Java SE 8
/*
문제 :
디스크의 원점과 반지름 길이가 주어진다.
각 디스크가 겹치는 개수를 출력하라
방법 :
1. 각 디스크의 최대점과 최저점을 각각 배열로 가지고 있는다.
2. 최대점 배열과 최저점 배열을 정렬 한다.
(정렬을 하면 최대점 배열은 원점의 위치를 고려한 낮은 값부터 높은 값 으로 정렬 되고
최저점 배열은 원점의 위치를 고려한 폭이 정렬된다.)
--> 반복
3. 최대점 배열의 처음의 값보다 최저점 배열의 값이 클때까지의 개수를 구한다.
(이 개수는 최대점 배열의 처음 값을 포함하는 디스크의 개수다)
4. 전체 값을 구할때 교차점 개수 + 최소점 개수 - 최대점 개수 - 1을한다.
(최대점과 -1을 빼는 이유는 중복값을 제거하기 위함이다.)
** 만약 10,000,000개의 넘는 교차점이 존재하면 -1을 출력한다.
5. 교차점의 개수를 출력한다.
*/
int length = A.length;
int[] upper_disc = new int[length];
int[] lower_disc = new int[length];
// 최대점 배열과 최저점 배열에 최대점,최저점을 구한다. 문제에 따라 식은 index가 원점,이 되고 index에 해당하는 값이 반지름이다.
for(int i=0; i < length; i++){
upper_disc[i] = i + A[i]; // 최대점 = 원점 + 반지름
lower_disc[i] = i - A[i]; // 최저점 = 원점 - 반지름
}
// 최대점과 최저점 배열을 정렬한다.
Arrays.sort(upper_disc);
Arrays.sort(lower_disc);
int lower_index = 0;
int upper_index = 0;
int intersection = 0;
// 교차점의 개수를 구한다. 기준은 최대점 배열이며 최대점보다 최저점이 작은 경우 최대점이 최저점에 포함된다.
for(upper_index=0; upper_index < length; upper_index++){
// 하나의 디스크와 겹쳐지는 다른 디스크의 개수를 구한다.
while(lower_index < length && upper_disc[upper_index] >= lower_disc[lower_index]){
lower_index++;
}
// 교차점에서 중복값을 제거하기 위해 upper_index-1을 한다.
intersection = intersection + lower_index - upper_index -1;
}
if(intersection < MAX)
intersection = -1;
return intersection;
}
}
Code: 09:05:37 UTC,
java,
verify,
result: Failed
1234567891011121314151617181920212223242526272829303132333435363738394041424344454647484950515253545556575859606162636465666768
// you can also use imports, for example:
import java.util.*;
// you can use System.out.println for debugging purposes, e.g.
// System.out.println("this is a debug message");
class Solution {
int MAX = 10000000;
public int solution(int[] A) {
// write your code in Java SE 8
/*
문제 :
디스크의 원점과 반지름 길이가 주어진다.
각 디스크가 겹치는 개수를 출력하라
방법 :
1. 각 디스크의 최대점과 최저점을 각각 배열로 가지고 있는다.
2. 최대점 배열과 최저점 배열을 정렬 한다.
(정렬을 하면 최대점 배열은 원점의 위치를 고려한 낮은 값부터 높은 값 으로 정렬 되고
최저점 배열은 원점의 위치를 고려한 폭이 정렬된다.)
--> 반복
3. 최대점 배열의 처음의 값보다 최저점 배열의 값이 클때까지의 개수를 구한다.
(이 개수는 최대점 배열의 처음 값을 포함하는 디스크의 개수다)
4. 전체 값을 구할때 교차점 개수 + 최소점 개수 - 최대점 개수 - 1을한다.
(최대점과 -1을 빼는 이유는 중복값을 제거하기 위함이다.)
** 만약 10,000,000개의 넘는 교차점이 존재하면 -1을 출력한다.
5. 교차점의 개수를 출력한다.
*/
int length = A.length;
int[] upper_disc = new int[length];
int[] lower_disc = new int[length];
// 최대점 배열과 최저점 배열에 최대점,최저점을 구한다. 문제에 따라 식은 index가 원점,이 되고 index에 해당하는 값이 반지름이다.
for(int i=0; i < length; i++){
upper_disc[i] = i + A[i]; // 최대점 = 원점 + 반지름
lower_disc[i] = i - A[i]; // 최저점 = 원점 - 반지름
}
// 최대점과 최저점 배열을 정렬한다.
Arrays.sort(upper_disc);
Arrays.sort(lower_disc);
int lower_index = 0;
int upper_index = 0;
int intersection = 0;
// 교차점의 개수를 구한다. 기준은 최대점 배열이며 최대점보다 최저점이 작은 경우 최대점이 최저점에 포함된다.
for(upper_index=0; upper_index < length; upper_index++){
// 하나의 디스크와 겹쳐지는 다른 디스크의 개수를 구한다.
while(lower_index < length && upper_disc[upper_index] >= lower_disc[lower_index]){
lower_index++;
}
// 교차점에서 중복값을 제거하기 위해 upper_index-1을 한다.
intersection = intersection + lower_index - upper_index -1;
}
if(intersection < MAX)
intersection = -1;
return intersection;
}
}
Code: 09:05:54 UTC,
java,
verify,
result: Passed
1234567891011121314151617181920212223242526272829303132333435363738394041424344454647484950515253545556575859606162636465666768
// you can also use imports, for example:
import java.util.*;
// you can use System.out.println for debugging purposes, e.g.
// System.out.println("this is a debug message");
class Solution {
int MAX = 10000000;
public int solution(int[] A) {
// write your code in Java SE 8
/*
문제 :
디스크의 원점과 반지름 길이가 주어진다.
각 디스크가 겹치는 개수를 출력하라
방법 :
1. 각 디스크의 최대점과 최저점을 각각 배열로 가지고 있는다.
2. 최대점 배열과 최저점 배열을 정렬 한다.
(정렬을 하면 최대점 배열은 원점의 위치를 고려한 낮은 값부터 높은 값 으로 정렬 되고
최저점 배열은 원점의 위치를 고려한 폭이 정렬된다.)
--> 반복
3. 최대점 배열의 처음의 값보다 최저점 배열의 값이 클때까지의 개수를 구한다.
(이 개수는 최대점 배열의 처음 값을 포함하는 디스크의 개수다)
4. 전체 값을 구할때 교차점 개수 + 최소점 개수 - 최대점 개수 - 1을한다.
(최대점과 -1을 빼는 이유는 중복값을 제거하기 위함이다.)
** 만약 10,000,000개의 넘는 교차점이 존재하면 -1을 출력한다.
5. 교차점의 개수를 출력한다.
*/
int length = A.length;
int[] upper_disc = new int[length];
int[] lower_disc = new int[length];
// 최대점 배열과 최저점 배열에 최대점,최저점을 구한다. 문제에 따라 식은 index가 원점,이 되고 index에 해당하는 값이 반지름이다.
for(int i=0; i < length; i++){
upper_disc[i] = i + A[i]; // 최대점 = 원점 + 반지름
lower_disc[i] = i - A[i]; // 최저점 = 원점 - 반지름
}
// 최대점과 최저점 배열을 정렬한다.
Arrays.sort(upper_disc);
Arrays.sort(lower_disc);
int lower_index = 0;
int upper_index = 0;
int intersection = 0;
// 교차점의 개수를 구한다. 기준은 최대점 배열이며 최대점보다 최저점이 작은 경우 최대점이 최저점에 포함된다.
for(upper_index=0; upper_index < length; upper_index++){
// 하나의 디스크와 겹쳐지는 다른 디스크의 개수를 구한다.
while(lower_index < length && upper_disc[upper_index] >= lower_disc[lower_index]){
lower_index++;
}
// 교차점에서 중복값을 제거하기 위해 upper_index-1을 한다.
intersection = intersection + lower_index - upper_index -1;
}
if(intersection > MAX)
intersection = -1;
return intersection;
}
}
Code: 09:06:03 UTC,
java,
verify,
result: Passed
1234567891011121314151617181920212223242526272829303132333435363738394041424344454647484950515253545556575859606162636465666768
// you can also use imports, for example:
import java.util.*;
// you can use System.out.println for debugging purposes, e.g.
// System.out.println("this is a debug message");
class Solution {
int MAX = 10000000;
public int solution(int[] A) {
// write your code in Java SE 8
/*
문제 :
디스크의 원점과 반지름 길이가 주어진다.
각 디스크가 겹치는 개수를 출력하라
방법 :
1. 각 디스크의 최대점과 최저점을 각각 배열로 가지고 있는다.
2. 최대점 배열과 최저점 배열을 정렬 한다.
(정렬을 하면 최대점 배열은 원점의 위치를 고려한 낮은 값부터 높은 값 으로 정렬 되고
최저점 배열은 원점의 위치를 고려한 폭이 정렬된다.)
--> 반복
3. 최대점 배열의 처음의 값보다 최저점 배열의 값이 클때까지의 개수를 구한다.
(이 개수는 최대점 배열의 처음 값을 포함하는 디스크의 개수다)
4. 전체 값을 구할때 교차점 개수 + 최소점 개수 - 최대점 개수 - 1을한다.
(최대점과 -1을 빼는 이유는 중복값을 제거하기 위함이다.)
** 만약 10,000,000개의 넘는 교차점이 존재하면 -1을 출력한다.
5. 교차점의 개수를 출력한다.
*/
int length = A.length;
int[] upper_disc = new int[length];
int[] lower_disc = new int[length];
// 최대점 배열과 최저점 배열에 최대점,최저점을 구한다. 문제에 따라 식은 index가 원점,이 되고 index에 해당하는 값이 반지름이다.
for(int i=0; i < length; i++){
upper_disc[i] = i + A[i]; // 최대점 = 원점 + 반지름
lower_disc[i] = i - A[i]; // 최저점 = 원점 - 반지름
}
// 최대점과 최저점 배열을 정렬한다.
Arrays.sort(upper_disc);
Arrays.sort(lower_disc);
int lower_index = 0;
int upper_index = 0;
int intersection = 0;
// 교차점의 개수를 구한다. 기준은 최대점 배열이며 최대점보다 최저점이 작은 경우 최대점이 최저점에 포함된다.
for(upper_index=0; upper_index < length; upper_index++){
// 하나의 디스크와 겹쳐지는 다른 디스크의 개수를 구한다.
while(lower_index < length && upper_disc[upper_index] >= lower_disc[lower_index]){
lower_index++;
}
// 교차점에서 중복값을 제거하기 위해 upper_index-1을 한다.
intersection = intersection + lower_index - upper_index -1;
}
if(intersection > MAX)
intersection = -1;
return intersection;
}
}
Code: 09:06:12 UTC,
java,
final,
score:
93
1234567891011121314151617181920212223242526272829303132333435363738394041424344454647484950515253545556575859606162636465666768
// you can also use imports, for example:
import java.util.*;
// you can use System.out.println for debugging purposes, e.g.
// System.out.println("this is a debug message");
class Solution {
int MAX = 10000000;
public int solution(int[] A) {
// write your code in Java SE 8
/*
문제 :
디스크의 원점과 반지름 길이가 주어진다.
각 디스크가 겹치는 개수를 출력하라
방법 :
1. 각 디스크의 최대점과 최저점을 각각 배열로 가지고 있는다.
2. 최대점 배열과 최저점 배열을 정렬 한다.
(정렬을 하면 최대점 배열은 원점의 위치를 고려한 낮은 값부터 높은 값 으로 정렬 되고
최저점 배열은 원점의 위치를 고려한 폭이 정렬된다.)
--> 반복
3. 최대점 배열의 처음의 값보다 최저점 배열의 값이 클때까지의 개수를 구한다.
(이 개수는 최대점 배열의 처음 값을 포함하는 디스크의 개수다)
4. 전체 값을 구할때 교차점 개수 + 최소점 개수 - 최대점 개수 - 1을한다.
(최대점과 -1을 빼는 이유는 중복값을 제거하기 위함이다.)
** 만약 10,000,000개의 넘는 교차점이 존재하면 -1을 출력한다.
5. 교차점의 개수를 출력한다.
*/
int length = A.length;
int[] upper_disc = new int[length];
int[] lower_disc = new int[length];
// 최대점 배열과 최저점 배열에 최대점,최저점을 구한다. 문제에 따라 식은 index가 원점,이 되고 index에 해당하는 값이 반지름이다.
for(int i=0; i < length; i++){
upper_disc[i] = i + A[i]; // 최대점 = 원점 + 반지름
lower_disc[i] = i - A[i]; // 최저점 = 원점 - 반지름
}
// 최대점과 최저점 배열을 정렬한다.
Arrays.sort(upper_disc);
Arrays.sort(lower_disc);
int lower_index = 0;
int upper_index = 0;
int intersection = 0;
// 교차점의 개수를 구한다. 기준은 최대점 배열이며 최대점보다 최저점이 작은 경우 최대점이 최저점에 포함된다.
for(upper_index=0; upper_index < length; upper_index++){
// 하나의 디스크와 겹쳐지는 다른 디스크의 개수를 구한다.
while(lower_index < length && upper_disc[upper_index] >= lower_disc[lower_index]){
lower_index++;
}
// 교차점에서 중복값을 제거하기 위해 upper_index-1을 한다.
intersection = intersection + lower_index - upper_index -1;
}
if(intersection > MAX)
intersection = -1;
return intersection;
}
}