활용 방안
자바의 경우 Comparable
을 활용해서 구현 가능
static class Element implements Comparable<Element> {
public int idx, num;
@Override
public int compareTo(Element other) {
return num - other.num;
}
// 음수 값이 나오면 내가 먼저, 양수 값이 나오면 other가 먼저
// 위 비교식은 오름차순 정렬
}
시간복잡도 : 약 O(N log N)
- 각종 복잡한 Sorting Algorithm들은 차치해두고 자바의
Arrays.sort(arr)
메소드를 기준으로 봤을 때 sort
메소드는 Primitive 원소의 경우 Dual-Pivot Quick Sort를, Object 원소의 경우 Tim Sort를 사용- O(N log N) 시간복잡도는 10만 개의 원소를 정렬하기 위해서 대략 160만 번의 연산을 수행
In-place / Stable
- In-place : N의 크기에 비하면 무시해도 될 만큼의 추가 메모리를 사용하는가?
- Stable : 비교해도 똑같은, 동등한 위상의 원소들은 순서 관계가 보존되는가?
특성
- 정렬하게 되면 같은 정보들은 항상 인접해 있음
- 정렬 후 가장 비슷한 순서의 다른 원소는 해당 원소의 양 옆
- 정렬만 해도 쉽게 풀리는 문제가 많음!
- 그러므로 O(N log N)이라는 시간복잡도는 충분히 지불할 만한 가치가 있음
문제 풀이
BOJ 1015 - 수열 정렬
- 난이도 : 2
- 배열 A의 값들과 배열 P의 index를 표시한 값들을 활용해서 배열 B를 만드는 문제
- N은 50 이하이므로, int 범위 안에서 충분히 표현 가능
static class Element implements Comparable<Element> {
public int num, idx;
@Override
public int compareTo(Element other) {
return num - other.num;
}
}
static int N;
static int[] P;
static Element[] B;
static void input() {
N = scan.nextInt();
B = new Element[N];
P = new int[N];
for (int i = 0; i < N; i++) {
B[i] = new Element();
B[i].num = scan.nextInt();
B[i].idx = i;
}
}
static void solve() {
Arrays.sort(B);
for (int i = 0; i < N; i++) {
P[B[i].idx] = i;
}
for (int i = 0; i < N; i++) {
sb.append(P[i]).append(' ');
}
System.out.println(sb);
}
public static void main(String[] args) {
input();
solve();
}
※ Scanner 클래스에 대한 코드는 생략해두었습니다. 😅
'Algorithm > 유형별 풀이 template' 카테고리의 다른 글
Two Pointers (0) | 2022.07.14 |
---|---|
Binary Search (0) | 2022.07.12 |
Brute Force (0) | 2022.07.10 |