https://codility.com/demo/results/demo5472KB-8BH/
-------------------------문제---------------------------
Given an array A of N integers, we draw N discs in a 2D plane such that the I-th disc is centered on (0,I) and has a radius of A[I]. We say that the J-th disc and K-th disc intersect if J ≠ K and J-th and K-th discs have at least one common point.
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 pairs of intersecting discs. For example, given N=6 and:
A[0] = 1 A[1] = 5 A[2] = 2 A[3] = 1 A[4] = 4 A[5] = 0
intersecting discs appear in eleven pairs of elements:
- 0 and 1,
- 0 and 2,
- 0 and 4,
- 1 and 2,
- 1 and 3,
- 1 and 4,
- 1 and 5,
- 2 and 3,
- 2 and 4,
- 3 and 4,
- 4 and 5.
so the function should return 11.
The function should return −1 if the number of intersecting pairs exceeds 10,000,000.
Assume that:
- N is an integer within the range [0..100,000];
- each element of array A is an integer within the range [0..2147483647].
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.
-------------------------풀이---------------------------
// 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; } }