Note)
- 선형 자료구조 -> list, array
- 정렬: 순서를 규칙에 맞게 바꾸는 것
1. Bubble sort
- 크기를 비교해서 작은 것을 왼쪽에 둔다.
- index 0 을 inde = 1 ~ n-1 까지의 값과 비교한다.
- index 1 을 inde = 2 ~ n-1 까지의 값과 비교한다. ...
- 시간 복잡도: O(n)
- 가장 느리고 확실
<hide/>
import java.util.Comparator;
import java.util.LinkedList;
import java.util.List;
public class BubbleSort implements Sortable {
public <T> List<T> sort(List<T> list , Comparator<T> comparator){
List<T> copy = new LinkedList<>(list);
int size = copy.size();
for(int i = 0; i < size; ++i) {
for(int j = i + i; j < size; ++j) {
T d1 = copy.get(i);
T d2 = copy.get(j);
if(comparator.compare(d1, d2) > 0) {
copy.set(i, d2);
copy.set(j, d1);
}
}
}
return copy;
}
}- 인자로 전달되는 list로부터 복사본 리스트인 copy를 만들고 순서를 교체해서 정렬 수행
- 제너릭 타입 T는 참조형
2. Insertion sort (삽입 정렬)
- 대소 비교해서 삽입한다.
- [ 3 1 5 2 4 ] 에 대해
-> 첫번째 원소3은 그냥 두고 1부터 보자.
-> 1을 기준으로 왼쪽의 3은 1보다 크다. => [ 1 3 5 2 4 ]
-> 다음으로 5기준으로 왼쪽을 보면 1, 3 즉 5보다 작은 값만 있다. => [ 1 3 5 2 4 ]
-> 2기준으로 보면, 3, 5는 2보다 크니까 두 칸 옮긴다. => [ 1 2 3 5 4 ]
-> 4기준으로 비교하여 옮긴다. => [ 1 2 3 4 5 ]
- 값을 하나씩 옮겨 간다.
- 시간 복잡도: O(n)
- Comparator 인터페이스는 Comparable 인터페이스와 같이 객체를 정렬하는 데 사용되는 인터페이스이다.
- Method generic type은 클래스에 제네릭 타입을 선언하지 않고 각 method마다 제네릭 타입을 선언 가능
-> <T> List<T>
<hide/>
import java.util.Comparator;
import java.util.LinkedList;
import java.util.List;
public class InsertSort implements Sortable {
@Override
public <T> List<T> sort(List<T> list, Comparator<T> comparator){
List<T> copy = new LinkedList<>(list);
int size = copy.size();
for(int i = 0 ; i < size ; ++i){
T d1 = copy.get(i);
for(int j = i - 1; j >= 0; --j) {
T d2 = copy.get(j);
if(comparator.compare(d1, d2) > 0 ) break;
copy.remove(j); // 기존 아이템을 제거해서
copy.add(j + 1, d2); // 특정 위치에 삽입한다.
}
}
return copy;
}
}
3. Selection sort
- 전체 데이터의 최솟값을 찾아가면서 가장 왼쪽에 옮기는 방식
- [ 3 1 5 2 4 ]의 최솟값: 1을 셀렉트해서 가장 왼쪽으로
=> [ 1 3 5 2 4 ]
- 뒤에 네 개중에서 최솟값은 2
=> [ 1 2 3 5 4 ]
- 뒤에 세 개중에서 최솟값은 3
=> [ 1 2 3 5 4 ]
- 뒤에 두 개중에서 최솟값은 4
=> [ 1 2 3 4 5 ]
- 범위가 하나니까 결국 끝
=> [ 1 2 3 4 5 ]
- 시간 복잡도: O(n^2)
<hide/>
package D220324;
import java.util.Comparator;
import java.util.LinkedList;
import java.util.List;
public class SelectionSort implements Sortable {
public <T> List<T> sort(List<T> list, Comparator<T> comparator){
List<T> copy = new LinkedList<>(list);
int size = copy.size();
for(int i = 0;i < size; ++i) {
int minIndex = 1;
T min = copy.get(i);
for(int j = i + 1; j < size; ++j) {
T d = copy.get(j);
if(min == null || comparator.compare(min, d) > 0 ) {
minIndex = j;
min = d; // 첫번째 요소를 min으로 먼저 지정하고 나머지 요소 중 min을 업데이트
}
}
copy.remove(minIndex);
copy.add(i, min);
}
return copy;
}
}4. Quick sort
- 작은 것들, 큰 것들끼리 나눠서 합친다.
- 시간 복잡도: best O(nlogn) / worst O(n^2) - pivot값에 따라 달라진다.
- 아무거나 pivot값으로 정한다.
- pivot을 기준으로 큰 값/ 작은 값으로 나눈다.
- 나눠진 그룹 안에서 새로운 피봇을 정하고 큰 값 / 작은 값으로 다시 나눈다.
- 이론적으로 가장 빠르다.
- [3 1 2 4 5] 에 대해 피봇을 5라고 하자.
-> (3 1 2 4) 에서 임의 피봇 2라고 한다.
-> ( 1 ) ( 3 4 ) 두 그룹으로 나뉜다.
-> 왼쪽 그룹에 1밖에 없으니 1 확정
-> 오른쪽 그룹에 피봇 정하고서 작은값 (3), 큰 값(4)로 나뉜다.
-> 작은 그룹 / 피봇/ 큰 그룹 모두 합쳐서 집어 넣는다.
<hide/>
import java.util.LinkedList;
import java.util.List;
import java.util.Objects;
import java.util.Random;
class MyData implements Comparable<MyData>{
int v;
public MyData(int v) {
this.v = v;
}
public String toString() {
return "" + v;
}
public int compareTo(MyData o) {
return Integer.compare(v, o.v);
}
@Override
public boolean equals(Object o) {
if(this == o) return true;
if(o == null || getClass() != o.getClass()) return false;
MyData mydata = (MyData) o;
return v== mydata.v;
}
@Override
public int hashCode() {
return Objects.hash(v);
// 같은 value가 들어가면 같은 해시값이 나온다.
// 키로 사용되는 것은 해시코드를 호출해서 나온 해시값을 이용해서 인덱스로 이용한다.
}
}
public class QuickSort {
public static void main(String[] args) {
List<MyData> list = new LinkedList<>();
Random r = new Random();
for(int i = 0; i < 20; ++i) list.add(new MyData(r.nextInt(50)));
System.out.println(list);
list = quickSort(list);
System.out.println(list);
}
static List<MyData> quickSort(List<MyData> list){
if(list.size() <= 1) return list;
MyData pivot = list.remove(0); // 맨 앞의 값을 임의로 피봇 설정
List<MyData> lesser = new LinkedList<>();
List<MyData> greater = new LinkedList<>();
for(MyData m : list) {
if(pivot.compareTo(m) > 0 ) lesser.add(m);
else greater.add(m);
}
List<MyData> merged = new LinkedList<MyData>();
merged.addAll(quickSort(lesser));
merged.add(pivot);
merged.addAll(quickSort(greater));
return merged;
}
}
<hide/>
import java.util.Comparator;
import java.util.LinkedList;
import java.util.List;
import java.util.function.Predicate;
import java.util.stream.Collectors;
public class QuickSort implements Sortable {
@Override
public <T> List<T> sort(List<T> list, Comparator<T> comparator) {
List<T> copy = new LinkedList<>(list);
return quickSort(copy, comparator);
}
private <T> List<T> quickSort(List<T> list, Comparator<T> comparator) {
if (list.size() <= 1) return list;
T pivot = list.remove(list.size() / 2);
List<T> lesser = quickSort(sublist(list, (d) -> comparator.compare(pivot, d) > 0), comparator);
List<T> greater = quickSort(sublist(list, (d) -> comparator.compare(pivot, d) <= 0), comparator);
return new LinkedList<T>() {{
addAll(lesser);
add(pivot);
addAll(greater);
}};
}
private <T> List<T> sublist(List<T> list, Predicate<T> filter) {
return list.stream().filter(filter).collect(Collectors.toList());
}
}- 재귀를 위해 내부에 quickSort메서드와 특정 조건에 맞는 값으로만 구성되는 부분리스트를 만드는 sublist 메서드를
- 별도로 만들어 활용한다.
- pivot 값을 리스트의 중값위치 값으로 설정한다.
- merge된 리스트를 반환하기 위해 double brace initialization을 사용한다.
5. Merge sort (병합 정렬)
- 시간 복잡도: O(nlogn)
- 일단 나눴다가 작은 것부터 합친다.
- [3 1 2 4 5]
-> [3 1 ] [2 4 5]
-> [3] [1] [2] [4 5]
-> [3] [1] [2] [4] [5] ... 하나씩 쪼개질 때까지 나눈다.
-> 그 다음에 대소 비교하면서 합친다.
-> [1] [3] [2] [ 4 5 ]
-> [ 1 3 ] [ 2 4 5 ]
-> 두 그룹의 가장 작은 값인 1, 2를 비교해서 1, 2를 차례로 넣는다. [1 2 ...] => [ 1 2 3 4 5 ]
<hide/>
import java.util.Comparator;
import java.util.LinkedList;
import java.util.List;
public class MergeSort implements Sortable {
public <T> List<T> sort(List<T> list, Comparator<T> comparator){
List<T> copy = new LinkedList<>(list);
return mergeSort(copy, comparator);
}
private <T> List<T> mergeSort(List<T> list, Comparator<T> comparator){
if(list.size() <= 1) return list;
int mid = list.size() / 2;
List<T> left = sort(list.subList(0, mid) , comparator); // list.subList를 통해 인덱스에 따른 sublist사용
List<T> right = sort(list.subList(mid, list.size()) , comparator);
List<T> merged = new LinkedList<T>();
while(!left.isEmpty() || !right.isEmpty()) { // left, right 중 하나라도 원소있으면 실행
if(left.isEmpty()) {
merged.addAll(right);
break;
}
if(right.isEmpty()) {
merged.addAll(left);
break;
}
T leftFirst = left.get(0);
T rightFirst = right.get(0);
if(comparator.compare(leftFirst, rightFirst) < 0) {
merged.add(left.remove(0));
}else {
merged.add(right.remove(0));
}
}
return merged;
}
}- sublist는 사이즈가 고정되어 있기 때문에 메서드 sort를 통해서 재귀시킴으로써 copy를 만든다.
Note) comparator란?
-> 인터페이스이며 compare를 구현해야한다.
-> 인터페이스이기 때문에 new 불가능
Note) toString
- ( "" + 값 ) 보다는 String.valueOf() 를 권장한다.
Note) compareTo
- (v -o.v)보다는 Integer.compare(v, o.v)를 권장.
Ex) 제일 작은 수 제거하기
- 정수를 저장한 배열에서 가장 작은 수를 제거한 배열을 리턴하는 함수 만들기
<hide/>
import java.util.*;
class Solution {
public int[] solution(int[] arr) {
if(arr.length == 1) return new int[] {-1}; // 원소가 1개이면 -1을 반환한다.
int min = Arrays.stream(arr).min().getAsInt(); // 최솟값을 찾는다.
return Arrays.stream(arr).filter(a -> a != min).toArray(); // 최솟값만 빼고 반환한다.
}
}<hide/>
import java.util.*;
class Solution {
public int[] solution(int[] arr) {
if(arr.length == 1) return new int[] {-1};
int min = Integer.MAX_VALUE;
for(int n: arr) if(n < min) min = n;
int [] answer = new int[arr.length - 1];
int index = 0;
for(int n : arr){
if(n == min) continue;
answer[index++] = n;
}
return answer;
}
}
Ex) 문자열 내마음대로 정렬하기
- 각각의 문자열에 대해 주어진 인덱스의 문자를 사전순으로 비교하여 나열한다.
<hide/>
import java.util.*;
class Solution {
public String[] solution(String[] strings, int n) {
Arrays.sort(strings, (s1, s2) -> { // n번째를 기준으로 정렬하기 위해 comparator
if(s1.charAt(n) == s2.charAt(n)) return s1.compareTo(s2);
// n번째 문자가 같은 경우, s1, s2를 사전순으로 정렬
return s1.charAt(n) - s2.charAt(n);
// n번째 문자가 각각 다른 경우, s1과 s2의 각각 n번째 글자를 기준으로 정렬한다.
});
return strings;
}
}
Ex) JadenCase 문자열 만들기
- JadenCase: 모든 단어의 첫 글자는 항상 대문자 (공백 다음도 대문자)
- 글자수만큼 스트링이 생성되는 것은 비효율적이므로 스트링 빌더, 스트링 버퍼를 이용하는게 더 좋다.
- append를 이용해 스트링 빌더에 누적해서 가지고 있다가 마지막에 toString으로 문자열 객체를 하나 만든다.
Sol 1)
<hide/>
class Solution {
public String solution(String s) {
String answer = "";
String s2 = s.toLowerCase();
char last = ' '; // 첫글자를 대문자로 바꾸기 위해 last의 초깃값 ' '으로 설정
for(char c : s2.toCharArray() ){
if(last == ' ') c = Character.toUpperCase(c); // 공백의 다음 글자를 대문자로 바꾼다.
answer += c; // 결괏값
last = c; // 마지막 글자
}
return answer;
}
}
Sol 2) 더 효율적인 방법
<hide/>
class Solution {
public String solution(String s) {
StringBuilder sb = new StringBuilder();
String s2 = s.toLowerCase();
char last = ' ';
for(char c : s2.toCharArray()){
if(last == ' ') c = Character.toUpperCase(c);
sb.append(c);
last = c;
}
return sb.toString();
}
}
- 1번의 경우 String을 이용하면 연산을 통해 새로운 문자열로 변경될 때마다 새로운 스트링 객체를 반환한다.
- 불필요한 스트링 객체가 연속 발생하며 프로그램의 성능이 저하될 수 있다.
-> StringBuilder클래스를 통해 새로운 객체를 만들지 않고 새롭게 문자 변경 작업하는 하는게 더 좋다.
Ex) H-index
- 먼저 sort를 이용해서 정렬한다.
- 그 다음 배열의 길이에서 인덱스를 빼준 값을 H에 저장한다. (H = citations.length - i)
-> H는 i번째 논문 보다 더 많이 이용된 논문들의 개수를 의미한다.
- citations[i]의 값이 H보다 크면 H-index 를 리턴하도록한다.
<hide/>
import java.util.*;
// 프로그래머스 lv 2 H-idx
//https://school.programmers.co.kr/learn/courses/30/lessons/42747
public class Test1 {
public static int solution(int[] citations) {
int answer = 0;
System.out.println();
Arrays.sort(citations); // [0 1 3 5 6 7 9]
System.out.println(Arrays.toString(citations));
for(int i = 0;i < citations.length; ++i){ // 1번 이상: 7개 , ... ,3번 이상 5개(length - i) 5번 이상 4개, 6번 이상 3개
int H = citations.length - i; // i번째 논문보다 많이 인용된 논문의 개수 카운트
if( citations[i] >= H){
System.out.printf("citation[%d] = %d >= %d %n", i, citations[i], H);
return H;
}
}
return 0;
}
public static void main(String[] args){
int[] arr1 = {3, 0, 6, 1, 5};
int[] arr2 = {3, 0, 6, 1, 5, 7, 2}; // 0 1 2 3 5 6 7
int[] arr3 = {3, 0, 6, 1, 5, 2, 4, 7, 8}; // 0 1 2 3 4 5 6 7 8
int[] arr4 = {3, 0, 6, 1, 5, 2, 4, 7, 8, 10, 11, 12, 13}; // 0 1 2 3 4 5 6 7 8 10 11 12 13
System.out.println(solution(arr1)); // 3
System.out.println(solution(arr2)); // 3
System.out.println(solution(arr3)); // 4
System.out.println(solution(arr4)); // 6
}
}
Note) 입출력 예시
'자료구조와 알고리듬 With Java > [프로그래머스] Algorithm' 카테고리의 다른 글
| Part 09 Tree (0) | 2022.03.28 |
|---|---|
| Part 08 Graph (그래프) (0) | 2022.03.24 |
| Part 06 선형탐색 (Linear Search) (0) | 2022.03.23 |
| Part 05 Stack과 Queue (0) | 2022.03.23 |
| Part 04 집합 (Set) (0) | 2022.03.22 |