Java 코딩테스트 공부/Java 코테 나만의 팁

Java 코딩테스트 공부/Java 코테 나만의 팁

[정렬] 객체를 비교하게 해주는 Comparable 인터페이스

x, y 좌표가 n개 주어진다고 하자. x를 기준으로 오름차순 정렬하는데 만약 x가 같다면 y를 기준으로 오름차순 정렬시켜라 라고 하는 문제가 있다면 정렬 기준을 설정해주어야한다. Comparable 인터페이스는 이러한 x, y 값을 가지는 객체간의 비교를 가능하게 해준다. import java.util.*; class Coords implements Comparable { public int x, y; Coords(int x, int y) { this.x = x; this.y = y; } // x값에 의해 정렬하고, x값이 같을 경우 y값에 의해 정렬한다. // CompareTo에서 양수를 리턴 : 두 객체의 자리가 바뀐다. // 음수 or 0을 리턴 : 두 객체의 위치가 바뀌지 않는다. @Overri..

Java 코딩테스트 공부/Java 코테 나만의 팁

[정렬] 내림차순 Arrays.sort(arr, Collections.reverseOrder());

그런데 int[] arr = new int[n]; 에서 이렇게 작성하면 오류 발생한다. 왜나하면 public static void sort(T[] a, Comparator

Java 코딩테스트 공부/Java 코테 나만의 팁

[정렬] 시간복잡도 O(N)를 가진 정렬 풀이법

basic : Scanner + Arrays.sort Scanner는 시간을 많이 잡아먹는데다, Arrays.sort는 평균 O(nlogn) 지만 최악의 경우 O(n2) 까지도 올라간다. =>BufferedReader, BufferedWriter(or StringBuilder) + Counting Sort 다만, Counting Sort가 많이 쓰이지 않는 이유는 K가 정렬할 수들 중에서 가장 큰 값을 의미하는데,만약 K가 N보다 작은 수이면 O(N)이 되지만, K가 N보다 매우 큰 수라면 시간복잡도가 엄청 커질 수 있다.예를 들어 10개 숫자 정렬하는데 가장 큰 숫자가 100일 경우엔 O(N^2)가 되고, 1000이라면 O(N^3)이 된다.즉, 정렬할 수들의 최대값에 영향을 받는 알고리즘이다. 따라서 ..

daramG
'Java 코딩테스트 공부/Java 코테 나만의 팁' 카테고리의 글 목록