Sort - [Java]
Sort
개념
1) compareTo()
2) comparator
3) PriorityQueue -> O(logN)
4) BinarySearch -> O(logN)
1) compareTo()
1) compareTo()
2) comparator
3) PriorityQueue -> O(logN)
4) BinarySearch -> O(logN)
A.compareTo(B)
1. A == B : 0
2. A > B : 1
3. A < B : -1
3번처럼 음수일 때는 오름차순으로 한다는 의미
2) Comparator
Comparaotr<Interval> Comp = new Comparator<Interval>() {
@Override
public int compare(Interval o1, Interval o2) {
return o1.end - o2.end;
}
};
문제
1. compareTo()
버전 번호 version1, version2를 비교하여 다음과 같치 반환한다.
1. version1 < version2 : -1 반환
2. version1 > version2 : 1 반환
3. version1 = version2 : 0 반환
Input : version1 = "8.5.2.4", version2 = "8.5.3"
Output : -1
풀이
- '.'으로 구분되어진 수를 문자열로 넣어준다. -> split을 이용하여 '.'을 기준으로 나누어 저장
- 앞자리 수부터 비교한다.
- 0이 나오면 동일하기 때문에 0이 아닐 때를 확인한다.
- "1.0.1" 과 "1" 이렇게 주어지는 경우가 있기 때문에 길이가 벗어나는 부분은 0으로 채워줘서 비교한다.
즉, 1,0,1 과 1,0,0 이 둘을 비교하는 것이다.
소스
public class Q1 {
public static void main(String[] args) {
String version1 = "8.5.2.4", version2 = "8.5.3";
// String version1 = "1.0.1", version2 = "1";
System.out.println(solve(version1, version2));
}
public static int solve(String v1, String v2) {
// 1. 각 문자열을 "."을 기준으로 숫자만 저장
String[] v1Arr = v1.split("\\.");
String[] v2Arr = v2.split("\\.");
// 2.
int len = Math.max(v1Arr.length, v2Arr.length);
for (int i = 0; i < len; i++) {
Integer v1Int = i < v1Arr.length ? Integer.parseInt(v1Arr[i]) : 0;
Integer v2Int = i < v2Arr.length ? Integer.parseInt(v2Arr[i]) : 0;
int comp = v1Int.compareTo(v2Int);
if (comp != 0) {
return comp;
}
}
return 0;
}
}
2. Comparator
버전 번호 version1, version2를 비교하여 다음과 같치 반환한다.
1. version1 < version2 : -1 반환
2. version1 > version2 : 1 반환
3. version1 = version2 : 0 반환
Input : version1 = "8.5.2.4", version2 = "8.5.3"
Output : -1
즉, 1,0,1 과 1,0,0 이 둘을 비교하는 것이다.
public class Q1 {
public static void main(String[] args) {
String version1 = "8.5.2.4", version2 = "8.5.3";
// String version1 = "1.0.1", version2 = "1";
System.out.println(solve(version1, version2));
}
public static int solve(String v1, String v2) {
// 1. 각 문자열을 "."을 기준으로 숫자만 저장
String[] v1Arr = v1.split("\\.");
String[] v2Arr = v2.split("\\.");
// 2.
int len = Math.max(v1Arr.length, v2Arr.length);
for (int i = 0; i < len; i++) {
Integer v1Int = i < v1Arr.length ? Integer.parseInt(v1Arr[i]) : 0;
Integer v2Int = i < v2Arr.length ? Integer.parseInt(v2Arr[i]) : 0;
int comp = v1Int.compareTo(v2Int);
if (comp != 0) {
return comp;
}
}
return 0;
}
}
특정한 객체의 값을 비교하여 Sorting하는 문제
start, end 가 주어졌을 때, 겹쳐지는 부분은 합치고 그렇지 않은 것은 그대로 반환
Input : [[1,3], [2,6], [8,10], [15,18]]
Output : [[1,6], [8,10], [15,18]]
설명) [1,3] 과 [2,6]은 서로 겹쳐지는 부분이 존재하여 [1,6]으로 합쳐진다.
풀이
- 주어지는 start 와 end 의 값을 start를 기준으로 정렬한다.
->정렬할 때 3가지 방법을 이용할 수 있다.
- 앞(before)의 end가 현재(current) start 보다 크거나 같으면 앞의 end를 둘 중 제일 긴 end로 갱신한다.
1번 방법)
Collections.sort(intervals, (a, b) -> a.start - b.start);
2번 방법)
public static Comparator<Interval> comp = new Comparator<>() {
@Override
public int compare(Interval o1, Interval o2) {
return o1.start - o2.start;
}
};
3번 방법)
public static Comparator<Interval> comp2 = new Comparator<>() {
@Override
public int compare(Interval o1, Interval o2) {
if (o1.start < o2.start) {
return -1;
} else if (o1.start > o2.start) {
return 1;
} else {
return 0;
}
}
};
소스
import java.util.*;
class Interval {
public int start;
public int end;
public Interval(int start, int end) {
this.start = start;
this.end = end;
}
}
public class Q2 {
public static void main(String[] args) {
Interval in1 = new Interval(1, 3);
Interval in3 = new Interval(2, 6);
Interval in2 = new Interval(8, 10);
Interval in4 = new Interval(15, 18);
List<Interval> intervals = new ArrayList<>();
intervals.add(in1);
intervals.add(in2);
intervals.add(in3);
intervals.add(in4);
List<Interval> list = merge(intervals);
print(list);
}
public static List<Interval> merge(List<Interval> intervals) {
if (intervals.isEmpty()) {
return intervals;
}
// 1. start를 기준으로 정렬
// Collections.sort(intervals, (a, b) -> a.start - b.start);
Collections.sort(intervals, comp);
List<Interval> result = new ArrayList<Interval>();
Interval before = intervals.get(0);
for (int i = 1; i < intervals.size(); i++) {
Interval current = intervals.get(i);
if (before.end >= current.start) {
before.end = Math.max(current.end, before.end);
} else {
result.add(before);
before = current;
}
}
if (!result.contains(before)) {
result.add(before);
}
return result;
}
public static Comparator<Interval> comp = new Comparator<>() {
@Override
public int compare(Interval o1, Interval o2) {
return o1.start - o2.start;
}
};
public static Comparator<Interval> comp2 = new Comparator<>() {
@Override
public int compare(Interval o1, Interval o2) {
if (o1.start < o2.start) {
return -1;
} else if (o1.start > o2.start) {
return 1;
} else {
return 0;
}
}
};
public static void print(List<Interval> list) {
for (Interval i : list) {
System.out.println(i.start + " " + i.end);
}
}
}
3. PriorityQueue
자바의 PriorityQueue 는 MinHeap으로 구성됨
양의 정수 길이의 두 막대기를 연결할 때 x 와 y의 비용을 지불한다.
이런식으로 연결하여 스틱이 하나 남을 때 까지 모든 스틱을 연결하는 최소 비용을 반환해라.Input : 스틱 = [1, 8, 3, 5]
Output : 30
설명)
1. 1 + 3 = 4 -> [4, 8, 5]
2. 4 + 5 = 9 -> [9, 8]
3. 9 + 8 = 17 -> [17]
총 비용 : 4 + 9 + 17 = 30
풀이
- PriorityQueue에 sticks 요소 하나씩 넣는다.
- pq.size() 가 1 보다 클때까지 while문을 돌려 합을 구한다.
- sum에 누적하면서 두 개의 수를 더한 값은 다시 큐에 넣는다.
- 구해진 합을 반환한다.
소스
import java.util.*;
public class Q3 {
public static void main(String[] args) {
int[] sticks = { 1, 8, 3, 5 };
System.out.println(solve(sticks));
}
public static int solve(int[] sticks) {
PriorityQueue<Integer> pq = new PriorityQueue<Integer>();
for (int i : sticks) {
pq.offer(i);
}
int sum = 0;
while (pq.size() > 1) {
int num1 = pq.poll();
int num2 = pq.poll();
int twoSum = num1 + num2;
sum += twoSum;
pq.offer(twoSum);
}
return sum;
}
}
4. Map + PriorityQueue
각 문자열에 대해서 빈도수가 높은 순으로 k만큼 해당 문자열을 반환
Input : {"i", "study", "inflearn", "i", "study", "coding"} , k = 2
Output : {"i", "study"}
제한) 빈도수가 동일 할 때 알파벳 순서가 낮은 단어가 먼저 온다.
Try to solve it in O(NlogN) time and O(n) extra space.
풀이
- Map을 이용하여 각 단어의 빈도수를 저장한다.
- 빈도수가 가장 높은 것부터 낮은 것 순으로 정렬한다.
- 빈도수가 동일할 때는 문자열의 알파벳이 낮은 순으로 정렬한다.
- 2번과 3번을 할 때 PriorityQueue를 이용해야 한다. (O(NlogN))
정렬 2가지 방법)
1번 방법 - 람다식
PriorityQueue<Map.Entry<String, Integer>> pq = new PriorityQueue<Map.Entry<String, Integer>>(
(a,b) -> a.getValue() == b.getValue() ? a.getKey().compareTo(b.getKey()) : b.getValue() - a.getValue());
2번 방법 - Comparator
PriorityQueue<Map.Entry<String, Integer>> pq = new PriorityQueue<Map.Entry<String, Integer>>(comp);
Comparator<Map.Entry<String, Integer>> comp = new Comparator<Map.Entry<String, Integer>>() {
@Override
public int compare(Entry<String, Integer> o1, Entry<String, Integer> o2) {
if (o1.getValue() == o2.getValue()) {
return o1.getKey().compareTo(o2.getKey());
}
return o2.getValue().compareTo(o1.getValue());
}
};
소스
import java.util.*;
import java.util.Map.Entry;
public class Q4 {
public static void main(String[] args) {
String[] words = { "i", "study", "inflearn", "i", "study", "coding" };
int k = 2;
System.out.println(solve(words, k));
}
public static List<String> solve(String[] words, int k) {
// 1.
List<String> result = new ArrayList<String>();
Map<String, Integer> map = new HashMap<String, Integer>();
for (String word : words) {
map.put(word, map.getOrDefault(word, 0) + 1);
}
// 2. pq -> 람다식
PriorityQueue<Map.Entry<String, Integer>> pq = new PriorityQueue<Map.Entry<String, Integer>>((a,
b) -> a.getValue() == b.getValue() ? a.getKey().compareTo(b.getKey()) : b.getValue() - a.getValue());
// 2. pq -> comparator
Comparator<Map.Entry<String, Integer>> comp = new Comparator<Map.Entry<String, Integer>>() {
@Override
public int compare(Entry<String, Integer> o1, Entry<String, Integer> o2) {
if (o1.getValue() == o2.getValue()) {
return o1.getKey().compareTo(o2.getKey());
}
return o2.getValue().compareTo(o1.getValue());
}
};
for (Map.Entry<String, Integer> entry : map.entrySet()) {
pq.offer(entry);
}
while (k-- > 0) {
result.add(pq.poll().getKey());
}
return result;
}
}
참고
인프런 강의 : 코딩테스트 전 꼭 알아야 할 개념과 문제(with 자바) - 푸샵맨 코딩스터디
Author And Source
이 문제에 관하여(Sort - [Java]), 우리는 이곳에서 더 많은 자료를 발견하고 링크를 클릭하여 보았다 https://velog.io/@minuk1236/Sort-Java저자 귀속: 원작자 정보가 원작자 URL에 포함되어 있으며 저작권은 원작자 소유입니다.
우수한 개발자 콘텐츠 발견에 전념 (Collection and Share based on the CC Protocol.)