[Kotlin] 코틀린으로 알고리즘 풀 때 필요한 것들

• 회사 주 언어는 코틀린인데 알고리즘은 파이썬으로 풀고 있어 효율이 좀 떨어지는 것 같아 코틀린으로 문제를 풀 예정이다. 계속 업데이트 할 예정.

1. 입력

val br = BufferedReader(InputStreamReader(System.`in`)) 
val input = br.readLine().toInt()

• BufferedReader를 사용해서 입력 값들을 받는다. 이유는 Scanner보다 빨라서

private val br = System.`in`.bufferedReader()
val (n, m) = br.readLine().split(' ').map { it.toInt() } // 공백 기준으로 정수 여러개 받기
val list =br.readLine().split(' ') // 리스트
println("$n $m")

val arr2 = Array(h) {
	Array(n) {
		readLine().split(" ").map { it.toInt() }.toIntArray() // 이차원 배열 받기

• 여러 개를 입력 받을 시 괄호를 친 이후, map을 이용한다.
• 여러 변수를 출력할 경우 문자열 안에 달러사인($)을 이용하면 출력 가능

ex) input이 4 (1,2) (1,3), (1,4), (1,5)일 때

  val input = MutableList(br.readLine().toInt()) {
    br.readLine().split(" ")
  }

• 이런 식으로 입력이 가능하다

2. 선형 자료구조

2-1. 배열

val arr1 = ArrayOf(1,2,3) 
var array = Array(3, { Array(4, {0}) }) // 3 x 4 배열
println(array.size) // 3

2-2. 리스트

val list1 = listOf(1, 2, 3) // 불변 객체 리스트
val list2 = mutableListOf<Int>(1,2,3) // 가변 객체 리스트
list2.removeAt(0) // 0번째 인덱스 원소 제거
list1.removeIf{ it == 1 } // 값이 1인 원소 전부 제거
list1.removeFirst() // 맨 앞 원소 제거
list1.removeLast() // 마지막 원소 제거

val alphabets = listOf('a', 'b', 'c')
println(alphabets.joinToString("")) 

• jointoString() 메서드로 char 리스트 이어서 출력 가능

2-3. 스택

val stack = MutableList<Int>(4) { it }

push
numbers.add(4)

pop
numbers.removeLast()

peek
numbers.last()

empty
numbers.isEmpty()

size
numbers.size

• 가변 리스트를 이용해 구현한다.

2-4. 큐

val que = LinkedList<Int>()

que.offer(3) // 원소 삽입

que.poll() // 원소 삭제 + 삭제한 원소 반환

que.peek() // 맨 앞 원소 반환

que.size() // 큐 사이즈 반환

• 맨 앞의 원소 삭제가 O(1)로 가능한 연결 리스트를 사용한다.

2-5. 덱

  val deque = ArrayDeque<Int>()
  
  deque.addFirst(0)
  deque.addLast(3)
  deque.add(1) // == addLast()

  deque.first()
  deque.peekFirst()
  deque.peek() // 첫 번째 원소 가져옴

  deque.last
  deque.peekLast() // 마지막 원소 가져옴

  deque.removeFirst(), deque.remove()
  deque.removeLast()
  
  deque.isEmpty() // 큐가 비었나 확인
  deque.size // 큐에 들어있는 원소 개수

  deque.clear() // 모두 삭제

• 스택, 큐를 이걸로 써도 무방함
• remove는 deque가 비어있으면 Exception, poll을 null을 리턴

2-6. 문자열

val s = "hello"
var s2 = StringBuilder(s)
s2[0] = 'a'
println(s2) // aello
s2.deleteAt(0) // 0번째 인덱스의 원소 제거
println(s2) // ello
var s3 = s2.slice(0..1) // slicing
println(se) // el

var s4 = " hello "
s4 = s4.trim()
println(s4) // "hello"

• String은 불변 객체라 인덱로 문자열 변경이 안된다. StringBuilder를 사용해서 인덱스로 문자열에 접근해서 value를 변경할 수 있다.
• slice() 메서드를 통해 슬라이싱 가능

3. 그래프

var graph = MutableList(n+1) { mutableListOf<Int>() } // 인접 리스트 방식으로 구현

val visited = BooleanArray(graph.size) { false } // 방문 여부 구현

4. MutableMap

val dict = mutableMapOf<String, Int>().withDefault { 0 }

dict["hello"] = 1 // set
dict.getValue("hello") // get

dict.key // key 목록을 가져온다.
dict.values // value 목록을 가져온다.
dict.entries // key=value

dict.containsKey("hello") // map에 key가 있는지 확인. 있으면 true 없으면 false
dict.containsValue(1) // map에 value가 있는지 확인. 있으면 true 없으면 false

5. 선형 자료구조 GroupBy로 Map 형태로 만들기

val numbers = listOf(1, 2, 3, 4, 5, 6)
val map = numbers.groupingBy { it }.eachCount() // {1=1, 2=1, 3=1, 4=1, 5=1, 6=1}

val str = "abcda"
val map = numbers.groupingBy { it }.eachCount() // {a=2, b=1, c=1, d=1}

• 파이썬의 defaultdict 모듈과 비슷하게 사용하기 위해 withDefault를 사용해 value를 0으로 초기화 했다.

6. Priority Queue

• 기본적으로 Min-Heap으로 동작한다.

// 기본 최소 힙
val heap = PriorityQueue<Int>()

// 최대 힙을 사용하기 위해 compareByDescending을 사용한다
val heap = PriorityQueue<Int>(compareByDescending { it })
        
// 힙에 추가
nums.forEach { heap.add(it) }
        
// 힙에서 delete
for (i in 1..k) {
   answer = heap.poll()
}

7. Kotlin Collections

https://soopeach.tistory.com/155