인프런 JAVA 알고리즘 정리(정렬 7번~10번)

7. 좌표정렬 // 일반 숫자 정렬이 아닌 좌표값을 정렬

- implements Comparable<클래스> 정렬 기준을 정할 수 있다.

- implements를 하면 정의해야 하는 compareTo 메서드를 정의해야 한다.

class Point implements Comparable<Point>{
    int x;
    int y;
    public Point(int x, int y){
        this.x = x;
        this.y = y;
    }

    @Override
    public int compareTo(Point o) {
        if(o.x == this.x) return this.y-o.y;
        return this.x-o.x;
    }
}

리턴해서 x를 기준으로 정렬을 한다면 this가 - 기호 앞에 오면 오름차순 this가 - 기호 뒤에 오면 내림차순 정렬

위의 코든는 x가 같으면 y를 기준으로 오름차순 정렬하고 같지 않으면 x를 기준으로 내림차순 정렬하는 코드

결과값

 

 

8. 이분검색 // 순차정렬이 아닌 반으로 줄이면서 해결

static int binarySearch(int[] arr, int s_num){
        Arrays.sort(arr);
        int start = 0;
        int end = arr.length;
        int mid = end/2;
        // start가 end보다 커지면 값이 없다는거
        while(start <= end) {
            if(arr[mid]==s_num) return mid+1;
            if (arr[mid] > s_num){
                end = mid-1;
                mid = (start+end)/2;
            }else{
                start = mid+1;
                mid = (start+end)/2;
            }
        }
        return 0;
    }

 

 

9. 뮤직비디오(결정알고리즘) 

// 핵심 - 이분탐색으로 결정가능한 최소 답안을 도출해라.

// 최소 9 부터 45 까지의 답안이 나올 수 있으며. 이 답안을 통하여 이분검색 실시하여 count 제한횟수 안에 가능하면 답안으로 채택가능

static int minimumNum(int[] arr, int dvd_num){
        int answer = 0;
        int lt = Arrays.stream(arr).max().getAsInt(); // 최소값
        int rt = Arrays.stream(arr).sum(); //최대값
        while(lt<=rt){ // 최소값을 찾는 과정
            int mid = (lt+rt)/2;
            if(count(arr, mid)<= dvd_num){ //설정한 제한 횟수 안에 가능한지
                // 가능하다면 최소값 설정
                answer = mid;
                rt = mid-1;
            }else{
                lt = mid+1;
            }
        }
        return answer;
    }

    static int count(int[] arr , int capacity){
        // 넘어온 값이 몇번 안에 가능한지
        int cnt = 1; //횟수
        int sum = 0;
        for(int x : arr){
            if(sum+x>capacity){
                cnt++;
                sum = x;
            }else sum+=x;
        }
        return cnt; //횟수 리턴
    }

// 초반 배열을 정렬하면 안되는 이유 =  각 비디오의 용량이 나와있고 문제의 요구사항에서 순서가 그대로 유지되어야 한다고 했다. 정렬을 하면 순서가 용량순으로 바뀌기 때문에 정렬을 하면 오답.

 

 

10. 마구간 정하기(결정알고리즘)

// 말을 놓을 수 있는 좌표가 주어짐 -> 말 사이의 거리를 구하는거기에 정렬 필요 

// 말 끼리의 거리는 멀면 멀수록 좋음 최소1 최대는 첫좌표 마지막좌표의 차이로 설정 ( 이진 탐색 )

// count 함수가 결정알고리즘의 핵심 포인트

static int minimumNum(int[] arr, int horse_num){
        Arrays.sort(arr);
        int answer = 0;
        int lt = 1; // 두 말의 최소 거리는 1
        int rt = arr[arr.length-1]-arr[0]; // 최대거리
        int mid = (lt+rt)/2;
        while(lt<=rt){
            // ex) 거리를 5로 했을때 말이 2마리 밖에 안들어간다면 else로 빠짐 -> 거리 감소
            // ex) 거리를 2로 했을때 말이 5마리 들어가서 상관이 없다. -> 거리 증가
            // 예시로 말이 3마리로 했으니 그 이상은 들어갈수 있어야된다.
            if(count(arr, mid)>=horse_num) {
                answer = mid;
                lt = mid+1;
            }else rt = mid-1;
            mid = (lt+rt)/2;
        }
        return answer;
    }

    static int count(int[] arr, int num ){ //유효한지 안한지
        int cnt = 1; //말이 들어간 개수
        int first = arr[0];
        for(int i=1; i<arr.length; i++){
            //거리 측정
            if(arr[i]-first>=num){
                cnt++;
                first = arr[i];
            }
        }
        return cnt;
    }