코딩 테스트 - NumberOfDiscIntersections

https://github.com/Mickey0521/Codility/blob/master/NumberOfDiscIntersections.java

이 사람 글 처럼 long을 써야 정상 처리된다!! (중요)

1안은 이거였음

package codility;

import java.util.Arrays;

public class NumberOfDiscIntersections_221223 {

    public static void main(String[] args) {

        int [] A = {1,5,2,1,4,0};

        solution(A);

    }

    public static int solution(int[] A) {

        // Implement your solution here

        int answer = 0;    

        int count = 0;

        /*

         * 0 - 1

         * 1 - 5

         * 2 - 2

         * 3 - 1

         * 4 - 4

         * 5 - 0 //5는 없음

         *

         *

         */

        int len = A.length;

       

        int [] start = new int[len];

        int [] end = new int[len];

        for(int i = 0; i < len; i++){

            start[i] = i - A[i];

            end[i] = i + A[i];

        }

        Arrays.sort(start);

        Arrays.sort(end);

        for(int i = 0; i < len; i++){

            여기서 로직을 잘못 짜서 ?????????? 가 되었음.

            중복 제거를 참조해야 한다!

        }

        System.out.println(answer);

        return answer;

    }

}

마지막 for문에서 오류를 내서 값이 마이너스가 됨... -.-)

교차점 추가 시에 중복 제거를 해줘야 한다고 함.

package codility;

import java.util.Arrays;

public class NumberOfDiscIntersections_221223 {

    public static void main(String[] args) {

        int [] A = {1,5,2,1,4,0};

        int a = solution(A);

        System.out.println(a);

    }

    public static int solution(int[] A) {

        // Implement your solution here

        /*

         * 0 - 1

         * 1 - 5

         * 2 - 2

         * 3 - 1

         * 4 - 4

         * 5 - 0 //5는 없음

         *

         *

         */

 

        int len = A.length;

        long[] start = new long[len]; //앞 지점

        long[] end = new long[len]; //뒤 지점

       

        for(int i=0; i<len; i++){

            start[i] = i - (long)A[i]; //시작점 - 값

            end[i] = i + (long)A[i]; //시작점 + 값

        }

       

        Arrays.sort(end); //정렬

        Arrays.sort(start); //정렬

       

        int answer = 0; //답 개수

        int count=0;  //지점 couter

       

        for(int i = 0; i < len; i++){

            while( count < len && end[i] >= start[count]){

                    answer = answer + count; //교차하는 지점 추가

                    answer = answer - i; //중복 제거용 i

                    count++;

            }          

        }

       

        if(answer > 10000000){

            return -1;

        } //overFlow 계산해야 한다고 함 (오류!)

       

        return answer;

    }

}

음 이것은 이차원 배열로 짜다가, start-end로 분기하는 것까지는 아이디어가 좋았으나,

중복 제거하는 로직까지는 참조하지 못했으므로 50% 승리한 것으로 count...