Sort
여러 정렬에 대한 개념과 문제 풀이
1. 개념
정렬이란 사용자가 정의한 순서로 데이터를 나열하는 것을 말한다.
1.1. 삽입 정렬
삽입 정렬은 데이터의 전체 영역에서 정렬된 영역과 정렬되지 않은 영역을 나누고 정렬되지 않은 영역의 값을 정렬된 영역의 적절한 위치로 놓으며 정렬한다.
삽입 정렬은 최악의 경우 O(N^2)이며 최선의 경우는 O(N)이다.
1.2. 병합 정렬
병합 정렬은 정렬되지 않은 영역을 쪼개서 각각의 영역을 정렬하고 이를 합치며 정렬한다.
나누는 횟수는 logN, 이를 합치는 횟수 NlogN(N개를 병합하는 과정을 logN번 진행)이다. 따라서 시간 복잡도는 O(NlogN)이다.
1.3. 힙 정렬
힙 정렬은 힙이라는 자료구조를 사용해 정렬한다.
힙은 특정 규칙이 있는 이진 트리이다. 그리고 규칙에 따라 최대힙, 최소힙으로 나눈다.
최대힙은 부모 노드가 자식 노드보다 크고, 최소힙은 부모 노드가 자식 노드보다 작다.
1.3.1. 최대 힙 구축 방법
- 현재 노드와 자식 노드의 값을 비교한다.
- 현재 노드의 값이 가장 크지 않으면 자식 노드 중 가장 큰 값과 현재 노드의 값을 바꾼다.
- 만약 자식 노드가 없거나 현재 노드의 값이 가장 크면 연산을 종료한다.
- 맞바꾼 자식 노드의 위치를 현재 노드로 하여 과정 1을 반복한다.
최대 힙 정렬 과정
- 정렬되지 않은 데이터로 최대힙을 구축한다.
- 현재 최대힙의 루트 노드와 마지막 노드를 맞바꾼다. 맞바꾼 뒤 마지막 노드는 최대힙에서 제외한다.
- 현재 최대힙은 마지막 노드가 루트 노드가 되었다. 따라서 최대힙을 다시 구축해야 한다.
1.3.2. 힙 정렬의 시간 복잡도
정렬되지 않은 값 N개를 힙으로 나타내면 높이가 logN인 트리가 된다.
데이터는 N개이므로 각 데이터에 대해 힙 정렬을 수행하면 시간 복잡도는 O(NlogN)이다.
1.4. 우선순위 큐
우선순위 큐는 우선순위가 높은 데이터부터 먼저 처리하는 큐이다.
우선순위 큐의 내부 동작은 힙과 유사하므로 우선순위 큐를 구현할 때는 힙을 활용하는 것이 효율적이다.
원소의 개수가 N이라고 할 때 시간 복잡도는 addAll()은 O(NlogN)이고, add() / poll() 메서드 둘 다 O(logN)이다.
1.5. 계수 정렬
데이터의 빈도수를 다 채운 후 우선순위가 높은 데이터부터 빈도수만큼 출력하는 것이 계수 정렬이다. 이처럼 빈도수를 세어 빈도수 배열에 저장하는 것이므로 저장할 값의 범위가 듬성듬성 있거나 음수가 있으면 비효율적이다.
계수 정렬의 시간 복잡도는 값의 범위 크기가 K라면 빈도수 배열에서 K + 1 만큼 탐색해야 하므로 계수 정렬의 시간 복잡도는 O(N + K)이다.
1.6. 위상 정렬
위상 정렬은 특별한 그래프에서 방문 순서를 결정하는 알고리즘이다.
위상 정렬은 일의 순서가 중요하므로 반드시 간선의 방향이 있어야 한다. 만약 그래프에 순환이 있고 간선의 방향이 없으면 일의 방향이 없는 것이므로 방향 비순환 그래프(DAG, directed acyclic graph)에서만 사용할 수 있다.
위상 정렬은 자신을 향한 화살표 개수를 진입차수로 정의하여 진행한다. 진입차수가 0인 일을 해결하고 관련된 작업의 진입차수를 1씩 낮추면서 새롭게 진입차수가 0이 된 작업들을 해결하는 식으로 진행한다.이 해결이라는 행위는 큐를 활용하여 구현한다.
위상 정렬의 시간 복잡도는 모든 정점과 간선을 딱 한 번씩만 지나므로 시간 복잡도는 O(|V| + |E|)가 된다.
1.7. 정렬 알고리즘의 시간 복잡도
| 정렬 방법 | 최악의 경우 | 최선의 경우 | 특이점 |
|---|---|---|---|
| 삽입 정렬 | O(N^2) | O(N) | 데이터가 거의 정렬되어 있을 때는 최고의 성능을 발휘한다. |
| 병합 정렬 | O(NlogN) | O(NlogN) | 안정적인 성능으로 정렬할 수 있다. 병합 과정에서 추가적인 메모리가 필요하다. |
| 힙 정렬 | O(NlogN) | O(NlogN) | 안정적인 성능으로 정렬할 수 있다. 데이터를 삽입과 동시에 빠르게 정렬할 수 있다. |
| 계수 정렬 | O(N+K) | O(N+K) | 데이터에 의존적이므로 항상 사용 가능한 것은 아니다. |
| 위상 정렬 | O(V+E) | O(V+E) | 작업의 순서가 존재할 때 사용되는 알고리즘이다. |
2. (문제) 문자열 내 마음대로 정렬하기
2.1. 설명
문자열로 구성된 리스트 strings와, 정수 n이 주어졌을 때, 각 문자열의 인덱스 n 번째 글자를 기준으로 오름차순으로 정렬하려 합니다. 예를 들어 strings가 [“sun”, “bed”, “car”] 이고 n이 1 이면 각 단어의 인덱스 1의 문자 “u”, “e”, “a”로 strings를 정렬한다.
2.2. 제약 조건
- strings는 길이 1 이상, 50 이하인 배열이다.
- strings의 원소는 소문자 알파벳으로 이루어져 있다.
- strings의 원소는 길이 1 이상, 100 이하인 문자열이다.
- 모든 strings의 원소 길이는 n보다 크다.
- 인덱스 1의 문자가 같은 문자열이 여럿이면, 사전순으로 앞선 문자열이 앞쪽에 위치한다.
2.3. 입출력의 예
| strings | n | return |
|---|---|---|
| [“sun”, “bed”, “car”] | 1 | [“car”, “bed”, “sun”] |
| [“abce”, “abcd”, “cdx”] | 2 | [“abcd”, “abce”, “cdx”] |
2.4. 코드
1
2
3
4
5
6
7
8
9
10
fun main() {
fun solution(strings: Array<String>, n: Int): Array<String> =
// 문자열의 n 번째 오름차순, 문자열 전체로 오름차순 정렬
strings
.sortedWith(compareBy({ it[n] }, { it }))
.toTypedArray()
val message = solution(arrayOf("sun", "ber", "bed", "car"), 1).toList()
println(message)
}