Codility Lesson 06 - NumberOfDiscIntersections( JAVA )

https://app.codility.com/programmers/lessons/6-sorting/number_of_disc_intersections/

NumberOfDiscIntersections coding task - Learn to Code - Codility

 

문제

- A배열은 N개의 양의 정수들의 배열로 0 ~ N-1까지의 숫자들의 디스크 집합이다.

- J-번쨰 디스크는 중점이 (J, 0)이고 반지름은 A[J]이다.

- J != K일 때 J, K-번째의 디스크들이 최소한 한개의 공통점이라도 가지면 교차한다고 한다.

- 예시

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.

- 예시에서는 11개의 교차점이 발생한다.

 

제한조건

• 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].

N은 0 ~ 100,000 사이의 정수이다.

A의 각각의 원소는 0 ~ 2,147,483,647 사이의 정수이다.

 

풀이

- 풀이방법이 전혀 생각 나지 않아 아래 블로그 참조( 다른 블로그는 봐도 이해가 잘 안되는...)

- 요약하자면, 기존에 생각했던 것과 같이 최소, 최대 값을 쌍으로 저장하고, 최소값을 기준으로 정렬 -> 비교기준의 하나를 잡고, 비교하고자하는 disc의 최소값이 비교기준의 최대값보다 작으면 intersection count를 +1하는 방법으로

 

https://miiingo.tistory.com/326

[Codility] Lesson 6: Sorting - NumberOfDiscIntersections (javascript) 문제 풀이

 

참고사이트

- java의 comparable, comparator

https://st-lab.tistory.com/243

자바 [JAVA] - Comparable 과 Comparator의 이해

 

구글링을 했음에도 결과는 절망적...

 

퍼포먼스며 정확도며.. 흠.. 대체적으로 정확한 이해 후 재풀이가 필요할 듯이보인다..( 집중력 한계ㅠ )

3/29 재풀이 도전

- 하위에는 참고한 사이트

https://darkstart.tistory.com/195

[Codility][Sorting] NumberOfDiscIntersections 풀이 해석

- youtube도 참고해보고

https://www.youtube.com/watch?v=HV8tzIiidSw 

 

유튜브를 참고한 풀이 부터 해보자

풀이

- lower( disc start point ), upper( disc end point )의 각각의 집합을 만들고 오름차순으로 정렬

- lower를 순회하면서 동시에 upper를 넘는지 안넘는지 확인.

- open된 disc의 개수를 확인하면서 intersection count를 한다.

 

// 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

        if( A.length < 2 ) return -1;

        long[] lower = new long[A.length];
        long[] upper = new long[A.length];

        // lower, upper 입력
        for( int i=0; i<A.length; i++ ){
            lower[i] = i - (long)A[i];
            upper[i] = i + (long)A[i];
        };

        Arrays.sort(lower);
        Arrays.sort(upper);

        int intersection = 0;
        int openDisc = 0;
        int j=0;    // upper index;

        for( int i=0; i<lower.length; i++ ){
            // close disc
            while( upper[j] < lower[i] && j<upper.length){
                openDisc -= 1;
                j++;
            }

            intersection += openDisc;
            openDisc++;
        }

        if( intersection > 10000000 ) return -1;

        return intersection;
    }
}

코너 케이스를 제대로 못잡은 듯.. 다시 도전!

 

최종 소스

// 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

		// 빈배열이거나 원이 1개만 존재할 경우( 교차점 X )
        if( A.length < 2 ) return 0;

        long[] lower = new long[A.length];
        long[] upper = new long[A.length];

        // lower, upper 입력
        for( int i=0; i<A.length; i++ ){
            lower[i] = i - (long)A[i];
            upper[i] = i + (long)A[i];
        };

        Arrays.sort(lower);
        Arrays.sort(upper);

        int intersection = 0;
        int openDisc = 0;
        int j=0;    // upper index;

        // i가 결국 openDisc 개수?
        for( int i=0; i<lower.length; i++ ){
            // close disc
            while( upper[j] < lower[i] && j<upper.length){
                openDisc -= 1;
                j++;
            }

            intersection += openDisc;
            openDisc++;
        }

        if( intersection > 10000000 ) return -1;

        return intersection;
    }
}

 

유튜브를 보고 이해는 했으나.. 다른 사람 풀이는 아직 이해 못한 상태..( 다음 기회에 포스팅하기로.. 도망 )

https://darkstart.tistory.com/195

[Codility][Sorting] NumberOfDiscIntersections 풀이 해석