# leetcode: 406. Queue Reconstruction by Height

kldaji·2022년 6월 29일
0

## leetcode

목록 보기
36/42

### sort

class Solution {
fun reconstructQueue(people: Array<IntArray>): Array<IntArray> {
// sort by h decreasing order. then, by k increasing order.
// k takes part of index of insertion.
people.sortWith(compareBy({-it[0]}, {it[1]}))
val result = mutableListOf<IntArray>()
for (person in people) {
}
return result.toTypedArray()
}
}

### binary tree

data class Node(val person: IntArray, var precedePersonIncludeMe: Int, var left: Node?, var right: Node?)

class Solution {
fun reconstructQueue(people: Array<IntArray>): Array<IntArray> {
// sort by h decreasing order. then, by k increasing order.
people.sortWith(compareBy({-it[0]}, {it[1]}))
val root = Node(people[0], 1, null, null)
val size = people.size
for (i in 1 until size) {
// If the number of precede person include target node, go to left with increasing precede person one.
// Else go to right with decreasing the number of precede person which means does not consider already passed precede person.
insertPerson(root, people[i], people[i][1])
}
val result = mutableListOf<IntArray>()
traverse(root, result)
return result.toTypedArray()
}

fun insertPerson(root: Node, person: IntArray, numOfPrecedePerson: Int) {
if (numOfPrecedePerson < root.precedePersonIncludeMe) {
if (root.left == null) {
root.left = Node(person, 1, null, null)
} else {
insertPerson(root.left!!, person, numOfPrecedePerson)
}
root.precedePersonIncludeMe += 1
} else { // numOfPrecedePerson >= root.precedePersonIncludeMe
if (root.right == null) {
root.right = Node(person, 1, null, null)
} else {
insertPerson(root.right!!, person, numOfPrecedePerson - root.precedePersonIncludeMe)
}
}
}

fun traverse(root: Node?, result: MutableList<IntArray>) {
root ?: return
traverse(root.left, result)
}