Sorting II #7
Comments
정렬 (Sorting)계수 정렬 (Counting Sort)
기수 정렬 (Radix Sort)
Comparison Sort와 Non-comparison Sort
문제 풀이백준 15688번: 수 정렬하기 5 (계수 정렬로 풀기)
import Foundation
let file = FileIO()
let N = file.readInt()
var arr = Array(repeating: 0, count: 2000001)
var (minN,maxN) = (0,2000000)
var ans = ""
(0..<N).forEach { _ in
let num = file.readInt()
minN = min(minN, num+1000000)
maxN = max(maxN, num+1000000)
arr[num+1000000] += 1
}
(minN...maxN).forEach { n in
guard arr[n] > 0 else { return }
ans += String(repeating: "\(n-1000000)\n", count: arr[n])
}
print(ans)
// 라이노님의 빠른 입력처리
final class FileIO {
private var buffer:[UInt8]
private var index: Int
init(fileHandle: FileHandle = FileHandle.standardInput) {
buffer = Array(fileHandle.readDataToEndOfFile())+[UInt8(0)]
index = 0
}
@inline(__always) private func read() -> UInt8 {
defer { index += 1 }
return buffer.withUnsafeBufferPointer { $0[index] }
}
@inline(__always) func readInt() -> Int {
var sum = 0
var now = read()
var isPositive = true
while now == 10
|| now == 32 { now = read() }
if now == 45{ isPositive.toggle(); now = read() }
while now >= 48, now <= 57 {
sum = sum * 10 + Int(now-48)
now = read()
}
return sum * (isPositive ? 1:-1)
}
@inline(__always) func readString() -> String {
var str = ""
var now = read()
while now == 10 || now == 32 { now = read() }
while now != 10 && now != 32 && now != 0 {
str += String(bytes: [now], encoding: .ascii)!
now = read()
}
return str
}
}백준 2910번: 빈도 정렬_ = readLine()
var dic = [Int: (Int,Int)]()
var ans = ""
readLine()!.split { $0 == " " }.enumerated().forEach {
let n = Int(String($0.element))!
dic[n, default: ($0.offset, 0)].1 += 1
}
print(dic.sorted {
$0.value.1 != $1.value.1 ? $0.value.1 > $1.value.1 : $0.value.0 < $1.value.0
}.map {
String(repeating: "\($0.key) ", count: $0.value.1)
}.joined()) |
|
#Counting Sort 수의 범위가 1000만 이하 일 때는 카운팅 소트를 쓰고, 아니라면 쓰지 않는 것이 좋음 15688번 수 정렬하기 (시간초과)절댓값인 경우 범위를 2배로 봐야한다는 것을 잊지 말 것. import Foundation
let N = Int(readLine()!)!
var arr = Array(repeating: 0, count: 2000001)
for _ in 0..<N {
let input = Int(readLine()!)!
arr[1000000+input] += 1
}
for idx in arr.indices {
guard arr[idx] != 0 else { continue }
var count = arr[idx]
let num = idx-1000000
while count != 0 {
print(num)
count -= 1
}
}
Radix Sort (라딕스 소트 / 기수정렬)자릿수를 이용해서 정렬을 수행하는 알고리즘으로, Couting Sort 응용에 해당한다. 1의 자릿수에 맞게 배열에 수를 넣어준다. 처음에는 1의 자리수가 같은 친구들끼리는 초반의 순서가 유지된다. 왜 421보다 502가 클까?100의 자리를 비교하고, 10의 자리를 비교하고 ,1의 자리를 비교하고 상대적 위치가 유지된 채로 정렬이 수행됨 자릿수의 최대갯수가 D라고 할 때, D번에 걸쳐서 Counting Sort 를 하는 것과 같다 라딕스 소트의 맹점한 개의 리스트에 N개의 원소를 전부 넣어야 할 수도 있으니, N칸의 배열로 만들어야 하는데, 공간의 낭비를 해결하려면 연결리스트나 동적 배열을 사용해야 하는데, STL을 사용하지 못하면 구현이 까다롭다 예제
p10[i]에 10^i 승을 넣고 싶다면 p10[0] - 1; 방식으로 해야 한다 p10[i] = pow(10, i) Comparison Sort, Non-comparison Sort버블머지퀵소트와 지금의 카운팅 래딕스 소트의 차이? 저번에 학습한 정렬들은 원소들 끼리 크기를 비교하는 과정이 있었는데, STL Sort코딩 테스트에서는 STL 의 Sort 함수를 써서 진행
정렬의 응용
|
BOJ 2910 빈도 정렬import Foundation
let input = readLine()!.components(separatedBy: " ").compactMap { Int($0) }
let (N, C) = (input[0], input[1])
let numbers = readLine()!.components(separatedBy: " ").compactMap { Int($0) }
var numberCount: [Int: Int] = [:]
for i in 0..<N {
numberCount[numbers[i], default: 0] += 1
}
let sorted = numberCount.sorted {
if $0.value == $1.value {
return numbers.firstIndex(of: $0.key)! < numbers.firstIndex(of: $1.key)!
}
return $0.value > $1.value
}
let result = sorted.reduce(into: []) {
$0 += Array(repeating: $1.key, count: $1.value)
}
.map(String.init)
.joined(separator: " ")
print(result)
import Foundation
// 입력 처리
let input = readLine()!.split(separator: " ").compactMap { Int($0) }
let (N, _) = (input[0], input[1])
let numbers = readLine()!.split(separator: " ").compactMap { Int($0) }
// 빈도 계산 및 정렬
var frequencyMap = [Int: (count: Int, firstIndex: Int)]()
for (index, number) in numbers.enumerated() {
if let (count, firstIndex) = frequencyMap[number] {
frequencyMap[number] = (count + 1, firstIndex)
} else {
frequencyMap[number] = (1, index)
}
}
let sortedNumbers = frequencyMap.sorted { (a, b) in
if a.value.count == b.value.count {
return a.value.firstIndex < b.value.firstIndex
}
return a.value.count > b.value.count
}.flatMap { Array(repeating: $0.key, count: $0.value.count) }
// 결과 출력
print(sortedNumbers.map(String.init).joined(separator: " ")) |
문제풀이BOJ 2910 빈도정렬 코드/*
1. 많이 나온 수는 맨 앞에 배치
2. 동일하게 나온 수는 맨 앞에 나온 것을 기준삼음
*/
struct Solution {
var total: Int
var index: Int
}
let input = readLine()!.split(separator: " ").map { Int($0)! }
let n = input[0],
c = input[1]
let message_array = readLine()!.split(separator: " ").map { Int($0)! }
var checkBox: [Int: Solution] = [:]
// 1.
for i in 0..<message_array.count {
if let _ = checkBox[message_array[i]] {
checkBox[message_array[i]]!.total += 1
checkBox[message_array[i]]!.index = min(checkBox[message_array[i]]!.index, i)
} else {
checkBox[message_array[i]] = Solution(total: 1, index: i)
}
}
// 2.
let sortedArray = checkBox.sorted { (lhs, rhs) -> Bool in
if lhs.value.total == rhs.value.total {
return lhs.value.index < rhs.value.index
}
return lhs.value.total > rhs.value.total
}
// 3.
var answer: [String] = []
for (key, value) in sortedArray {
for i in 0..<value.total {
answer.append(String(key))
}
}
print(answer.joined(separator: " ")) |
9/20
The text was updated successfully, but these errors were encountered: