출처: https://www.boostcourse.org/mo234/lecture/154316?isDesc=false

Set

• 정해진 순서가 없는 요소들의 집합
• 집합의 개념이기 때문에 동일한 요소를 중복해서 가질 수 없다.
• 불변형은 setOf(), 가변형은 mutableSetOf() 함수로 생성

Set

package chap05.section2

fun main() {
    val mixedTypeSet = setOf("Hello", 5, "world", 3.14, 'c')
    val intSet: Set<Int> = setOf<Int>(1, 4, 5, 5, 5) 
    println(mixedTypeSet)
    println(intSet) // 중복된 요소 중에 하나만 출력 
}

[Hello, 5, world, 3.14, c]
[1, 4, 5]

MutableSet

package chap05.section2

fun main() {
    val animals = mutableSetOf("Lion", "Dog", "Cat", "Python", "Hippo")
    animals.add("Dog") // 이미 존재하므로 변화 없음.
    println(animals)
    animals.remove("Python")
    println(animals)
}

[Lion, Dog, Cat, Python, Hippo]
[Lion, Dog, Cat, Hippo]

Set을 구현하는 자료구조

HashSet

• hashSetOf() 함수로 Set을 생성하면, 해시 테이블에 요소를 저장할 수 있는 자바의 HashSet을 반환한다.
• HashSet은 불변성 선언이 없기 때문에 기본적으로 추가 및 삭제가 가능하다.
• HashSet의 요소들은 입력 순서와 상관없이 내부적으로 키에 따라 배치된다. (해시 함수에 따라 요소가 배치될 뿐이며, 정렬 기능은 제공하지 않는다.)

package chap05.section2

fun main() {
    val intHashSet: HashSet<Int> = hashSetOf(6, 3, 4, 7)
    println(intHashSet)
    
    intHashSet.add(8)
    intHashSet.remove(4)
    println(intHashSet)
}

[3, 4, 6, 7]
[8, 3, 6, 7]

cf) 해시 자료구조: 해시 함수를 이용해 특정 키에 대응하는 값을 평균 O(1)의 시간복잡도로 찾을 수 있는 자료구조 (해시 충돌이 발생하는 최악의 경우 O(N)까지 시간복잡도가 늘어날 수 있음.)

TreeSet

• sortedSetOf() 함수로 Set을 생성하면, 자바의 TreeSet을 정렬된 상태로 반환한다.
• java.util.* 패키지를 import 해야 한다.
• TreeSet은 저장된 데이터의 값에 따라 정렬 (이진 탐색 트리의 단점을 보완한 레드-블랙 트리 자료구조 사용)
• TreeSet은 HashSet 보다 데이터의 추가 및 삭제 연산이 오래 걸리지만, 검색과 정렬이 뛰어나다는 장점을 갖고 있다.

이진 탐색 트리, Red-Black 트리

이진 탐색 트리는 평균 O(logN)의 시간복잡도를 보장하지만, 트리가 한쪽으로 편향되는 경우 높이가 N에 가깝기 때문에 O(N)까지 시간복잡도가 늘어날 수 있다.

레드-블랙 트리는 노드를 Red와 Black 색상으로 구분하여, 최악의 경우에도 O(logN) 시간복잡도를 보장해주는 자가 균형 트리 중에 하나다.

package chap05.section2

import java.util.*

fun main() {
    val intSortedSet: TreeSet<Int> = sortedSetOf(4, 1, 7, 2)
    
    intSortedSet.add(6) 
    intSortedSet.remove(1) 
    println(intSortedSet) // 오름차순 정렬된 결과 
    
    intSortedSet.clear() 
    println(intSortedSet) 
}

[2, 4, 6, 7]
[]

LinkedHashSet

• linkedSetOf() 함수로 Set을 생성하면, 자바의 LinkedHashSet을 반환한다.
• LinkedHashSet은 연결 리스트로 구현된 해시 테이블을 이용한 자료구조
• 연속된 메모리 공간이 아니어도 비어있는 공간을 포인터로 가리켜 요소를 추가할 수 있으므로 메모리 공간의 효율적인 사용 가능
• 데이터의 추가, 삭제 용이
• 일반적인 HashSet보다 느리다고 한다.

package chap05.section2

import java.util.*

fun main() {
    val linkedHashSet: LinkedHashSet<Int> = linkedSetOf(4, 1, 7, 2)
    linkedHashSet.add(6) 
    linkedHashSet.remove(1) 
    println(linkedHashSet) 
    
    linkedHashSet.clear() 
    println(linkedHashSet) 
}

[4, 7, 2, 6]
[]

---

Map

• 키(key)와 값(value)으로 구성된 요소를 저장
• 키는 중복될 수 없지만 값은 중복 저장될 수 있다. (만약 기존에 저장된 키와 동일하면, 기존의 값은 없어지고 새로운 값으로 대체)
• 불변형은 mapOf(), 가변형은 mutableMapOf() 함수로 생성

Map

val map: Map<key type, value type> = mapOf(key to value [, ...])

package chap05.section2

fun main() {
    val langMap: Map<Int, String> = mapOf(11 to "Java", 22 to "Kotlin", 33 to "C++")
    
    for((key, value) in langMap){
        println("key = $key, value = $value")
    }
    
    println("langMap[22] = ${langMap[22]}")
    println("langMap.get(22) = ${langMap.get(22)}")
    println("langMap.keys = ${langMap.keys}")
}

key = 11, value = Java
key = 22, value = Kotlin
key = 33, value = C++
langMap[22] = Kotlin
langMap.get(22) = Kotlin
langMap.keys = [11, 22, 33]

MutableMap

package chap05.section2

fun main() {
    val capitalCityMap: MutableMap<String, String> =
    	mutableMapOf("Korea" to "Seoul", "China" to "Beijing", "Japan" to "Tokyo")
        
    println(capitalCityMap.keys)
    println(capitalCityMap.values)

    capitalCityMap.put("UK", "London")
    capitalCityMap.remove("China")
    println(capitalCityMap)

    val addData = mutableMapOf("USA" to "Washington")
    capitalCityMap.putAll(addData) // 맵 자체를 추가
    println(capitalCityMap)
}

[Korea, China, Japan]
[Seoul, Beijing, Tokyo]
{Korea=Seoul, Japan=Tokyo, UK=London}
{Korea=Seoul, Japan=Tokyo, UK=London, USA=Washington}

Map을 구현하는 자료구조

• Map에서도 자바의 HashMap, SortedMap, LinkedHashMap 같은 자료구조를 사용할 수 있다.
• hashMapOf(), sortedMapOf(), linkedMapOf()
• SortedMap은 기본적으로 키에 대해 오름차순 정렬된 형태로 사용
• 내부 구조는 앞서 설명했던 Set의 구조와 비슷하게 해시, 트리, 연결 리스트의 자료구조로 구현

package chap05.section2

import java.util.SortedMap

fun main() {
    val hashMap: HashMap<Int, String> = hashMapOf(1 to "Hello", 2 to "World")
    println("hashMap: $hashMap")

    val sortedMap: SortedMap<Int, String> = sortedMapOf(2 to "Apple", 1 to "Banana")
    println("sortedMap: $sortedMap") // 키에 대해 오름차순 정렬 

    val linkedHashMap: LinkedHashMap<Int, String> = linkedMapOf(1 to "Computer", 2 to "Mouse")
    println("linkedHashMap: $linkedHashMap")
}

hashMap: {1=Hello, 2=World}
sortedMap: {1=Banana, 2=Apple}
linkedHashMap: {1=Computer, 2=Mouse}