[정렬]

[blossun]

Comparable 구현

• List

 public static List<Person> arr = new ArrayList<>();
 Collections.sort(arr);

 private static class Word implements Comparable<Word> {
 private Integer length;
 private String str;

 public Word(String str) {
 this.length = str.length();
 this.str = str;
 }

 @Override
 public int compareTo(Word o) {
 if (this.length < o.length) {
 return -1;
 } else if (this.length == o.length) {
 return this.str.compareTo(o.str); //동일한 단어라면 0이 리턴되고 중복이 제거되고 저장된다. 그리고 알파벳 순서로 정렬됨
 } else {
 return 1;
 }
 }
 }

Comparator 정렬기준

// array
Arrays.sort(arr, Comparator.comparingInt(a -> a[1])); // a[1]를 기준으로 오름차순 정렬
// list
stringList.sort((num1, num2) -> (num2 + num1).compareTo(num1 + num2)); // 30, 3 -> 303, 330 중 330이 먼저

• sorted() - new Comparator

import java.util.Arrays;
import java.util.Comparator;

public class N12915 {
 private int N;

 public String[] solution(String[] strings, int n) {
 N = n;
 String[] results = Arrays.stream(strings).sorted(new Comparator<String>() {
 @Override
 public int compare(String o1, String o2) {
 int result = o1.charAt(n) - o2.charAt(n);
 if (result == 0) {
 return o1.compareTo(o2);
 }
 return result;
 }
 }).toArray(String[]::new);
 return results;
 }
}

• 문제 : 21.02.11 [프로그래머스] 12915 문자열 내 마음대로 정렬하기 #126

Multi 정렬 - thenComparing

fileNameList.sort(Comparator.comparing(FileName::getHead).thenComparing(Comparator.naturalOrder()));

[blossun]

Merge

• 두 배열 합치기
• Stable Sort 유지

 private static int[] solution(int[] arr1, int[] arr2) {
 int idx1 = 0;
 int idx2 = 0;
 int idxResult = 0;
 int arr1Len = arr1.length;
 int arr2Len = arr2.length;
 int[] result = new int[arr1Len + arr2Len];

 while (true) {
 if (idx1 == arr1Len && idx2 == arr2Len)
 return result;
 if (idx1 == arr1Len) {
 for (int j = idx2; j < arr2Len; j++) {
 result[idxResult++] = arr2[j];
 }
 return result;
 }
 if (idx2 == arr2Len) {
 for (int j = idx1; j < arr1Len; j++) {
 result[idxResult++] = arr1[j];
 }
 return result;
 }
 if (arr1[idx1] <= arr2[idx2]) {
 result[idxResult++] = arr1[idx1++];
 } else {
 result[idxResult++] = arr2[idx2++];
 }
 }
 }

Merge Sort

 public static int N;
 public static int[] arr;
 public static int[] tmp;

 public static void main(String[] args) throws IOException {
 BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
 StringBuilder sb = new StringBuilder();
 N = Integer.parseInt(br.readLine());
 arr = new int[N];
 tmp = new int[N];
 for (int i = 0; i < N; i++) {
 arr[i] = Integer.parseInt(br.readLine());
 }
 mergeSort(0, arr.length);
 for (int i : arr) {
 sb.append(i).append('\n');
 }
 System.out.println(sb);
 }

 private static void mergeSort(int st, int en) {
 if (en == st + 1)
 return ;
 int mid = (st + en) / 2;
 mergeSort(st, mid);
 mergeSort(mid, en);
 merge(st, en);
 }

 private static void merge(int st, int en) {
 int mid = (st + en) / 2;
 int lidx = st;
 int ridx = mid;

 for (int i = st; i < en; i++) {
 if (lidx == mid) tmp[i] = arr[ridx++];
 else if (ridx == en) tmp[i] = arr[lidx++];
 else if (arr[lidx] <= arr[ridx]) tmp[i] = arr[lidx++];
 else tmp[i] = arr[ridx++];
 }

 System.arraycopy(tmp, st, arr, st, en - st);
 }

[blossun]

입력과 동시에 빠른 정렬

input : 8 1 7 3 1
sorted : 1 1 3 7 8

int[] arrA = Arrays.stream(br.readLine().split(" ")).mapToInt(Integer::parseInt).sorted().toArray();

[blossun]

PriorityQueue에 정렬 순서 주입

 PriorityQueue<Job> pq = new PriorityQueue<>(new Comparator<Job>() {
 @Override
 public int compare(final Job o1, final Job o2) {
 return o1.workingTime - o2.workingTime;
 }
 });

[blossun]

Value를 기준으로 Map을 정렬하기 - Map.Entry

https://devlog-wjdrbs96.tistory.com/138

Key를 기준으로 Map을 정렬 - TreeMap

[Java] Comparable와 Comparator의 차이와 사용법

https://gmlwjd9405.github.io/2018/09/06/java-comparable-and-comparator.html

• 21.06.23 [프로그래머스] 카카오 블라인드 실패율 #211