정렬
정렬이란, 데이터 집합을 적합한 순서로 배치하는 것!
아래 이미지를 보면 숫자, 문자열로 오름차순이나 사전순으로 정렬을 한 것을 볼 수 있다.
예를 들어서 나이가 어린 사람이 먼저 정렬되고 나이가 같다면 이름이 빠른 사람을 정렬시킨다면 아래 이미지처럼 정렬이 된다
정렬을 하기위해서는 필요한 것
- 정렬할 데이터가 필요하다
- 정렬할 순서가 필요하다
아래 코드는 ALPS식 투표에서 사용한 내림차순으로 정렬하는 함수이다.
sortScroes함수에는 Score[] arr를 정렬하려하고 조건은 if (arr[j].scr < arr[i].scr)가 된다.
/// score 클래스를 내림차순 정렬하는 함수
public static void sortScroes(Score[] arr) {
for (int i=0; i<arr.length; i++) {
for (int j=0; j<i; j++) {
if (arr[j].scr < arr[i].scr) {
Score cur = arr[i]
for (int k=i; k>j; k--)
arr[k] = arr[k-1]
arr[j] = cur;
break;
}
}
}
}
유명한 정렬 알고리즘
N^2 정렬 알고리즘
- Bubble Sort, Selection Sort, Insertion Sort
NlogN 정렬 알고리즘
- QuickSort, Merge Sort, Heap Sort
그 외
- Counting Sort, Radix Sort, Bucket Sort
- Counting Sort 같은 경우 [10989] 수정렬하기3에서 푼적이 있다.
기본적인 정렬 함수 JAVA.Arrays.sort
- 배열을 정렬하는 Sort 함수가 존재한다
- int 배열의 Arrays.sort 같은 경우 오름차순으로 정렬이 된다.
- int[] numbers = { 6, 2, 3, 7, 5, 1, 4}; Arrays.sort(numbers); for (int number: numbers) System.out.println(number);
- String 배열의 Arrays.sort 같은 경우 사전순으로 정렬 된다.
- String[] names = {"Alice", "Erin", "Grace"} Arrays.sort(names); for(String name: names) System.out.println(name);
- int[], string[], boolean[], char[], byte[], short[], long[], double[], float[]
- 모두 값이 작은 순서대로 오름차순 정렬이 지원된다.
각 타입에 따라 사용되는 sort 종류가 다르다.
- String[] sort 경우 ComparableTimSort를 사용한다.
- Object type 배열의 정렬
- int[] sort 경우 DualPivotQuicksort를 사용한다
- primitive type 배열의 정렬
Object[] Sort
- 알고리즘: Tim Sort
- 평균 시간 복잡도: O(NlogN)
- 최악 시간 복잡도: O(NlogN)
- stable이 보장됨(stable이란, 안정적이라는 것) 아래 이미지를 예시로 보면 같은 값을 가진 값이라면 입력 순서가 먼저인 것이 먼저 배치
- 내림차순 정렬, Collections.reverseOrder() 사용
Integer[] objectArray = {6, 2, 3, 7, 5, 1, 4};
Arrays.sort(objectArray, Collections.reverseOrder());
for (Integer x : objectArray)
System.out.println(x);
Primitive[] sort
- 알고리즘: Dual-Pivot Quick Sort
- 평균 시간 복잡도: O(NlogN)
- 최악 시간 복잡도: O(N^2)
- stable이 보장되지 않음 아래 예시 이미지를 보면 같은 값을 가진 값이라면 어떤 순서도 가능하다, 즉 un-stable
- 내림차순 정렬, 반복문을 사용하여 거꾸로 출력
Integer[] primitiveArray = {6, 2, 3, 7, 5, 1, 4};
Arrays.sort (primitiveArray);
for (int i = primitiveArray.length - 1; i>=0; i--)
System.out.println(primitiveArray[i]);
[2751] 수 정렬하기 2
위의 문제를 예시로 sort의 시간복잡도를 테스트 해보자.
문제는 최대 1,000,000개의 정수를 오름차순으로 정렬하는 문제이다.
백만개의 정수를 입력받아야하니 BufferedReader와 BufferedWriter를 사용해서 입출력을 하겠다.
Arrays.sort(arr)를 사용해서 정렬했다.
결과는 시간초과가 발생한다.
그 이유는 Dual-Pivot Quick Sort가 최악의 경우 N^2이기 때문이다.
/// Int[].sort, **Dual-Pivot Quick Sort**
class Main {
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
int N = Integer.parseInt(br.readLine());
int[] arr = new int[N];
for(int i=0; i<N; i++)
arr[i] = Integer.parseInt(br.readLine());
Arrays.sort(arr);
BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
for(int i=0; i<N; i++)
bw.write(arr[i] + "\\n");
bw.flush();
}
}
그렇다면 Dual-Pivot Quick Sort를 사용하지 않고 Tim Sort를 사용하기 위해서 데이터 타입을 변환하자
int[] arr = new int[N]; ⇒ Intger[] arr = new Integer[N];
Arrays.sort(arr); ⇒ Tim Sort 즉, 최악의 경우에도 NlogN이다.
결과를 보면 시간초과가 나지 않고 맞은 모습을 볼 수 있다.
이렇게 같은 Arrays.sort같지만 다른 sort를 사용하고 있기에 데이터 타입마다 sort의 특징을 알면 알고리즘을 작성하는데 많은 도움이 된다!
/// Integer[].sort, **Tim Sort**
class Main {
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
int N = Integer.parseInt(br.readLine());
Integer[] arr = new Integer[N];
for(int i=0; i<N; i++)
arr[i] = Integer.parseInt(br.readLine());
Arrays.sort(arr);
BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
for(int i=0; i<N; i++)
bw.write(arr[i] + "\\n");
bw.flush();
}
}
단어정렬
시간 제한 메모리 제한 제출 정답 맞힌 사람 정답 비율
| 2 초 | 256 MB | 209702 | 88703 | 66369 | 40.595% |
문제
알파벳 소문자로 이루어진 N개의 단어가 들어오면 아래와 같은 조건에 따라 정렬하는 프로그램을 작성하시오.
- 길이가 짧은 것부터
- 길이가 같으면 사전 순으로
단, 중복된 단어는 하나만 남기고 제거해야 한다.
입력
첫째 줄에 단어의 개수 N이 주어진다. (1 ≤ N ≤ 20,000) 둘째 줄부터 N개의 줄에 걸쳐 알파벳 소문자로 이루어진 단어가 한 줄에 하나씩 주어진다. 주어지는 문자열의 길이는 50을 넘지 않는다.
출력
조건에 따라 정렬하여 단어들을 출력한다.
처음 문제풀이
이 문제는 조건이 3개가 있다.
- 길이가 짧은 단어부터 긴 단어로 오름차순 정렬하기
- 만약 단어가 중복된 단어라면 하나로 합치기
- 단어 길이가 같은 단어가 있다면 사전순으로 정렬하기
위의 조건들을 만족하는 알고리즘을 작성해보자. (알파벳은 소문자만 있으며, 단어의 개수 (1 ≤ N ≤ 20,000))
0. 예제 입력받기
/// 0. 입력 받기
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
int N = Integer.parseInt(br.readLine());
String[] words = new String[N];
for(int i=0; i<N; i++) {
words[i] = br.readLine();
}
1. 짧은 단어 기준으로 오름차순 정렬하기
1.1 단어 길이가 같은 단어가 있다면 사전순으로 정렬하기
Arrays.sort를 사용하여 길이가 같으면 사전 순으로 정렬하고 길이가 다르면 길이에 따라 정렬하는 메서드를 사용했다.
/// 1. 짧은 단어 기준으로 오름차순 정렬하기
Arrays.sort(words, (a, b) -> {
if (a.length() == b.length()) {
return a.compareTo(b); // 1.1 길이가 같으면 사전 순으로 정렬
}
return Integer.compare(a.length(), b.length()); // 1. 길이에 따라 정렬
});
2. 만약 단어가 중복된 단어라면 하나로 합치기
중복된 단어를 제거하려고 보니 처음 입력부터 제거를 하면 좋겠다고 생각했다.
그래서 HashSet을 사용해서 중복을 제거하고 다시 Array로 변경하려고 한다.
Set<String> wordsSet = new HashSet<>();
for(int i=0; i<N; i++) {
String word = br.readLine();
wordsSet.add(word);
}
// Set을 Array로 변환하여 정렬
String[] words = wordsSet.toArray(new String[wordsSet.size()]);
3. 출력하기
// 3. 출력하기
for (String word : words) {
bw.write(word + "\\n");
}
bw.flush();
전체 코드
import java.io.*;
import java.util.*;
class Main {
public static void main(String[] args) throws IOException {
/// 0. 입력 받기
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
int N = Integer.parseInt(br.readLine());
/// 2. 중복 제거하기
Set<String> wordsSet = new HashSet<>();
for (int i = 0; i < N; i++) {
String word = br.readLine();
wordsSet.add(word);
}
// Set을 Array로 변환
String[] words = wordsSet.toArray(new String[0]);
/// 1. 짧은 단어 기준으로 오름차순 정렬하기
Arrays.sort(words, (a, b) -> {
if (a.length() == b.length()) {
return a.compareTo(b); // 1.1 길이가 같으면 사전 순으로 정렬
}
return Integer.compare(a.length(), b.length()); // 1. 길이에 따라 정렬
});
// 3. 출력하기
for (String word : words) {
bw.write(word + "\\n");
}
bw.flush();
}
}
시간복잡도
이 알고리즘의 시간복잡도는
- 입력 받기: O(n)
- 중복 제거: O(N)
- Set을 Array로 변환: O(N)
- Arrays.sort(words, (a, b) -> {...}: O(N log N)
즉, 전체 시간 복잡도는 O(N log N)이다.
두 번째 문제풀이
이번에는 Set을 사용하지 않고 풀어보겠다.
0. 입력받기
Scanner sc = new Scanner(System.in);
int N = sc.nextInt();
String[] words = new String[N];
for (int i =0 ; i< N; i++)
words[i] = sc.next();
1. 길이가 짧은 것부터
2. 길이가 같으면 사전순으로
Comparator는 java.util에 속하는 인터페이스로 두객체를 비교하는 메서드를 정의한다.
음수는 o1<o2, 양수는 o1>o2, 0은 o1==o2
compareTo 메서드는 사전순으로 정렬한다.
Arrays.sort(words, new Comparator<String>() {
@Override
public int compare(String o1, String o2) {
if (o1.length() == o2.length())
return o1.compareTo(o2);
return o1.length() - o2.length();
}
});
3. 중복된 단어는 하나만 남기고 제거하고 출력하기
배열에 중복된 단어들이 양옆으로 나열되어있으니 맨처음을 출력해주고
순차적으로 비교하여 값이 같다면(equals) 출력하지 않게 한다.
System.out.println(words[0]);
for (int i=1; i<N; i++)
if (!words[i].equals(words[i-1]))
System.out.println(words[i]);
전체 코드
import java.util.*;
class Main {
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
int N = sc.nextInt();
String[] words = new String[N];
for (int i =0 ; i< N; i++)
words[i] = sc.next();
// 1. 길이가 짧은 것 부터
// 2. 길이가 같으면 사전 순으로
Arrays.sort(words, new Comparator<String>() {
@Override
public int compare(String o1, String o2) {
if (o1.length() == o2.length())
return o1.compareTo(o2);
return o1.length() - o2.length();
}
});
// 3. 중복된 단어는 하나만 남기고 제거해야 한다.
System.out.println(words[0]);
for (int i=1; i<N; i++)
if (!words[i].equals(words[i-1]))
System.out.println(words[i]);
}
}
시간복잡도
이 알고리즘의 시간복잡도는 O(L * NlogN) 이다. L: 문자열의 길이이다.
나이순 정렬
시간 제한 메모리 제한 제출 정답 맞힌 사람 정답 비율
| 3 초 | 256 MB | 162026 | 73536 | 56581 | 43.918% |
문제
온라인 저지에 가입한 사람들의 나이와 이름이 가입한 순서대로 주어진다. 이때, 회원들을 나이가 증가하는 순으로, 나이가 같으면 먼저 가입한 사람이 앞에 오는 순서로 정렬하는 프로그램을 작성하시오.
입력
첫째 줄에 온라인 저지 회원의 수 N이 주어진다. (1 ≤ N ≤ 100,000)
둘째 줄부터 N개의 줄에는 각 회원의 나이와 이름이 공백으로 구분되어 주어진다. 나이는 1보다 크거나 같으며, 200보다 작거나 같은 정수이고, 이름은 알파벳 대소문자로 이루어져 있고, 길이가 100보다 작거나 같은 문자열이다. 입력은 가입한 순서로 주어진다.
출력
첫째 줄부터 총 N개의 줄에 걸쳐 온라인 저지 회원을 나이 순, 나이가 같으면 가입한 순으로 한 줄에 한 명씩 나이와 이름을 공백으로 구분해 출력한다.
문제풀이
이 문제는 나이가 작은 순서대로 오름차순 정렬을 하면 되는 문제이다.
이 때 나이가 같다면 먼저 들어온 순서대로 정렬을 하면 된다. 즉 입력 순서대로 정렬을 하는 것.
0. 데이터를 묶기 위해서 Class 생성
1. 나이 순으로 정렬
2. 나이가 같다면 들어온 순서대로 정렬
여기서 이름은 따로 조건에 필요하지 않지만 출력하기 위해 age, name을 묶으려고 Class Member를 생성한다.
이 때 나는 Comparable를 implements를 하여 compareTo Method를 사용할 것이다.
age, name, idx를 받아서 정렬을 할 것이다 age는 나이를 비교하기 위해 name은 출력하기 위해 idx는 나이값이 같다면 들어온 순서대로 정렬하기 위해
// 0. 데이터를 묶기 위해서 Class 생성
static class Member implements Comparable<Member> {
int age;
String name;
int idx;
Member(int age, String name, int idx) {
this.age = age;
this.name = name;
this.idx = idx;
}
// 1. 나이 순으로 정렬하기
// 2. 나이가 같다면 들어온 순서대로 정렬하기.
@Override
public int compareTo(Member o) {
if (this.age != o.age)
return this.age - o.age;
return this.idx - o.idx;
}
}
3. 출력하기
main 클래스를 보게되면 Arrays.sort를 하여 정렬을 시켜준다.
Member 클래스에서 정의된대로 정렬이 실행되는 것이다.
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
int N = sc.nextInt();
Member[] members = new Member[N];
for(int i=0; i<N; i++)
members[i] = new Member(sc.nextInt(), sc.next(), i);
// 1. 나이가 작은 회원 먼저
// 2. 나이가 같으면 먼저 가입한 사람 먼저
Arrays.sort(members);
for (Member member: members )
System.out.println(member.age + " " + member.name);
}
4. 사실 idx는 필요없다!
이렇게 Main에서 적어준 sort를 보면 ComparableTimSort를 실행하는 것을 알 수 있다.
ComparableTimSort는 Stable하기 때문에 들어온 순서대로 정렬을 시켜준다. 그러므로 idx를 제거하고 실행해도 문제가 없다!
import java.util.Scanner;
import java.util.Arrays;
class Main {
static class Member implements Comparable<Member> {
int age;
String name;
Member(int age, String name) {
this.age = age;
this.name = name;
}
@Override
public int compareTo(Member o) {
return this.age - o.age;
}
}
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
int N = sc.nextInt();
Member[] members = new Member[N];
for(int i=0; i<N; i++)
members[i] = new Member(sc.nextInt(), sc.next());
// 1. 나이가 작은 회원 먼저
// 2. 나이가 같으면 먼저 가입한 사람 먼저
Arrays.sort(members);
for (Member member: members )
System.out.println(member.age + " " + member.name);
}
}
시간복잡도
이 알고리즘의 시간복잡도는 Arrays.sort 시간복잡도인데 ComparableTimSort 이니 O(NlogN)이다.
'알고리즘 > Sort' 카테고리의 다른 글
| [코딩테스트] [1931] 회의실 배정 (2) | 2024.12.11 |
|---|---|
| [코딩테스트] [18870] 좌표 압축 & [2910] 빈도 정렬 (0) | 2024.12.10 |
| [코딩테스트] Comparator & [7785] 회사에 있는 사람 & [1302] 베스트셀러 (2) | 2024.12.09 |