A zero-indexed 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.
Assume that:
- 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].
Complexity:
- expected worst-case time complexity is O(N*log(N));
- expected worst-case space complexity is O(N),
beyond input storage (not counting the storage required for input arguments).
Elements of input arrays can be modified.
=======================================================================
우리는 평면에 N개의 디스크를 그린다. 디스크 들은 0 부터 N - 1로 번호가 매겨진다.
디스크의 반지름으로 구분되는 N개의 음수가 아닌 정수 배열 A가 주어진다.
J번째 디스크는 중앙이 (J, 0)이고 반지름 A[J] 으로 그려진다.
J ≠ K이고 J번째 디스크와 K번째 디스크가 적어도 하나의 공통 지점이 있다면(디스크에 경계선도 포함한다고 가정한다.)
J번째 디스크와 K번째 디스크가 '교차'(intersect)한다고 말한다.
N = 6이고 A가 다음과 같다면 디스크들이 그려진 도형은 아래처럼 보여진다:
A[0] = 1
A[1] = 5
A[2] = 2
A[3] = 1
A[4] = 4
A[5] = 0
11개의 디스크가 교차하는 쌍이 11개(정렬되지 않은) 있다:
디스크 1과 디스크 4는 서로 교차하고, 다른 모든 디스크들과 교체한다;
디스크 2도 디스크 0, 디스크 3과 교차한다.
함수 작성:
class Solution { public int solution(int[] A); }
위에 설명한 것 같은 N개의 디스크로 표현되는 배열 A가 주어지고, 교차되는 디스크 쌍의 갯수(정렬되지 않은)를 리턴한다.
교차 쌍이 10,000,000를 초과하면 함수는 -1을 리턴해야 한다.
위에서 본 배열 A가 주어지면, 위에서 설명한 것 처럼 함수는 11을 리턴해야한다.
가정:
- N은 [0..100,000] 범위의 정수;
- A의 각 요소는 [0..2,147,483,647] 범위의 정수.
복잡도:
- 최악의 시간 복잡도는 O(N*log(N));
- 최악의 공간 복잡도는 O(N), 입력 공간 제외.
입력된 배열의 요소는 수정할 수 있다.
62%:
https://codility.com/demo/results/trainingEYPYR6-UPQ/
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
| /** | |
| * Correctness : 100% | |
| * Performance : 25% | |
| * Task : 62% | |
| */ | |
| public int solution1(int[] A){ | |
| int N = A.length; | |
| long result = 0; | |
| for (int i = 0; i < N - 1; i++) { | |
| for (int j = i + 1; j < N; j++) { | |
| long iMax = Math.min((long)i + A[i], N); | |
| long jMin = Math.max((long)j - A[j], 0); | |
| if (iMax >= jMin) { | |
| result++; | |
| if (result > 10E6) { | |
| return -1; | |
| } | |
| } | |
| } | |
| } | |
| return (int) result; | |
| } |
100%:
https://codility.com/demo/results/trainingAF88MJ-ZAP/
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
| /** | |
| * Task : 100% | |
| */ | |
| public static int solution(int[] A){ | |
| class Circle { | |
| long min; | |
| long max; | |
| } | |
| int N = A.length; | |
| Circle[] circles = new Circle[N]; | |
| for (int i = 0; i < N; i++) { | |
| Circle circle = new Circle(); | |
| circle.min = (long)i - A[i]; | |
| circle.max = (long)i + A[i]; | |
| circles[i] = circle; | |
| } | |
| Arrays.sort(circles, new Comparator<Circle>() { | |
| @Override | |
| public int compare(Circle o1, Circle o2) { | |
| if (o1.min > o2.min) { | |
| return 1; | |
| } else { | |
| return -1; | |
| } | |
| } | |
| }); | |
| int count = 0; | |
| for (int i = 0; i < N - 1; i++) { | |
| for (int j = i + 1; j < N && circles[i].max >= circles[j].min; j++) { | |
| count++; | |
| if (count > 10E6) { | |
| return -1; | |
| } | |
| } | |
| } | |
| return count; | |
| } |
