[프로그래머스] 특이한 정렬 - Kotlin(코틀린)

문제

정수 n을 기준으로 n과 가까운 수부터 정렬하려고 합니다. 이때 n으로부터의 거리가 같다면 더 큰 수를 앞에 오도록 배치합니다. 정수가 담긴 배열 numlist 와 정수 n이 주어질 때 numlist의 원소를 n으로부터 가까운 순서대로 정렬한 배열을 return 하도록 solution 함수를 완성해주세요.

제한사항

• 1 <= n <= 10,000
• 1 <= numlist의 원소 <= 10,000
• 1 <= numlist의 길이 <= 100
• numlist는 중복된 원소를 갖지 않습니다.

입출력 예

numlist	n	result
[1, 2, 3, 4, 5, 6]	4	[4, 5, 3, 6, 2, 1]
[10000, 20, 36, 47, 40, 6, 10, 7000]	30	[36, 40, 20, 47, 10, 6, 7000, 10000]

 

---

코드(Kotlin) - 내 코드

class Solution {
    fun solution(numlist: IntArray, n: Int): IntArray {
        val arr = ArrayList<Int>()
        for(num in numlist) {
            arr.add(num)
        }
        
        arr.sortWith { a, b ->
            if(abs(a - n) == abs(b - n)) {
                if(a > b) -1 else 1
            } else {
                abs(a - n) - abs (b - n)
            }
        }
        return arr.toIntArray()
}

코드(Kotlin) - 다른 사람 코드

class Solution {
    fun solution(numlist: IntArray, n: Int): IntArray {
        return numlist.sortedWith { a, b ->
            if(abs(a - n) == abs(b - n)) b.compareTo(a) else abs(a - n).compareTo(abs(b - n))
        }.toIntArray()
    }
}

풀이 과정

사실 처음 접근했던 방법은 아래 코드와 같이 map을 활용한 방법이었다. 그러나 아래 코드를 실행시켜봤을 때 일부 테스트케이스에서 시간초과가 발생하였기 때문에 다른 방법을 사용하여 구현을 하게되었다.

 

1. numlist가 담긴 ArrayList를 sortWith 를 사용하여 정렬을 한다.

2. 해당 정렬방법은 입력값 n 과의 절댓값을 기준으로 오름차순 정렬을 하는 방법이다. 이때 절댓값이 서로 같은 경우, 절댓값이 더 큰 값을 우선으로 정렬하도록 구현하였다.

 

코드가 정상적으로 실행된 후, 다른 사람의 코드를 찾아보니 내가 작성한 코드와 흐름은 비슷하지만 좀 더 간결하게 작성할 수 있는 방법이 있었다. 괄호 안에 담긴 a와 b의 크기를 비교하여 -1, 0, 1 을 반환하는 b.compareTo(a) 를 활용한 방법이었다.

코틀린을 사용하여 알고리즘 공부를 하기로 결심한 이상, 간결하게 사용할 수 있는 코틀린 문법들을 더 익혀둬야겠다는 생각이 들었다.

 

* 시행착오 코드 (일부 테스트케이스에서 시간초과 발생 - map 활용)

class Solution {
    fun solution(numlist: IntArray, n: Int): IntArray {
        var map = LinkedHashMap<Int, Double>()
        for(num in numlist) {
            map[num] = if(num > n) (num - n).toDouble() else (n - num + 0.5)
        }
        map = map.toList().sortedBy { it.second }.toMap() as LinkedHashMap<Int, Double>
        
        return map.keys.toIntArray()
    }
}

풀이과정)

주어진 입력값 n과 크기가 같다면 큰 수를 우선으로 정렬해야 하기 때문에 절댓값이 같은 두 수(음수, 양수)가 있다면 양수에 +0.5를 하여 절댓값이 같더라도 더 큰 수를 구별할 수 있도록 구현하였다.

꽤나 신선한 풀이방법이라고 생각했지만, 안타깝게도 해당 코드는 일부 테스트케이스에서 시간초과가 발생하였다. sortWith를 사용하여 정상적인 코드를 완성한 후, 해당 코드를 수정해볼까 했지만 다른 사람의 코드를 보니 map으로 작성된 코드는 없었다. 이 문제에서만큼은 map으로 작성한 코드는 효율적이지 않다는 판단이 들어 추가 수정은 하지 않았다.

(시행착오에 대한 기록 정도로 생각하기 위해 해당 코드도 본 게시물에 적어두는 바이다.)

---

알게된 내용

본 게시물에서는 위 코드를 작성하면서 알게된 "정렬하는 방법"에 대해 다뤄보려고 한다.

1. Map 정렬

Map 정렬은 Key를 기준으로 한 정렬과 Value를 기준으로 한 정렬로 나눌 수 있다.

var map = mutableMapOf<Int, String>(3 to "bbb", 1 to "ccc", 2 to "aaa")

//Key 기준 정렬
var arr: List<Int> = map.keys.sorted() //[1, 2, 3]
var arr: List<MutableMap.MutableEntry<Int, String>> = map.entries.sortedBy { it.key } //[1=ccc, 2=aaa, 3=bbb]
var arr: MutableMap<Int, String> = map.toSortedMap() //{1=ccc, 2=aaa, 3=bbb}
map.toSortedMap(compareByDescending { it }) //위 코드 내림차순 정렬

//Value 기준 정렬
var arr: List<String> = map.values.sorted() //[aaa, bbb, ccc]
var arr: List<MutableMap.MutableEntry<Int, String>> = map.entires.sortedBy { it.values } //[2=aaa, 3=bbb, 1=ccc]
var arr: MutableMap<Int, String> = map.toList().sortedBy { it.second }.toMap() as MutableMap //{2=aaa, 3=bbb, 1=ccc}
map.toList().sortedByDescending { it.second }.toMap() as MutableMap //위 코드 내림차순 정렬
//toList() 로 변환 시 List는 Pair<Key, Value> 로 구성

2. List 정렬

수정이 불가한 리스트(ImmutableList)는 sorted() 함수를, 수정이 가능한 리스트(MutableList)는 sort() 함수를 사용하여 정렬할 수 있다.

sorted()함수의 경우 리스트의 원본을 변경하지 않고 정렬된 리스트를 생성하여 리턴하는 반면, sort() 함수는 리스트 자신이 갖고 있는 요소의 순서를 변경한다.

//수정 불가한 리스트 (ImmutableList)
val immutableList = listOf(1, 3, 5, 2, 4)
val sortedList = immutableList.sorted() //오름차순 정렬
val reversedSortedList = sortedList.reversed() //내림차순 정렬

//수정 가능한 리스트 (MutableList)
val mutableList = mutableListOf(1, 3, 5, 2, 4)
mutableList.sort() //오름차순 정렬
mutableList.reverse() //내림차순 정렬

3. sortedWith(), sortWith()

수정이 불가한 리스트(ImmutableList)에 사용하는 sortedWith() 함수와 수정이 가능한 리스트(MutableList)에 사용하는 sortWith() 함수는 Comparator를 변경하여 자신이 원하는 조건으로 리스트를 정렬할 수 있다.

sortedWith() 함수는 sorted() 함수와 마찬가지로 정렬된 새로운 리스트를 반환하고, sortWith() 함수는 sort() 함수와 마찬가지로 자기 자신을 정렬한다.

val list = listOf("aaaaa", "bbb", "cccc", "d", "ee")
val comparator: Comparator<String> = compareBy<String> { it.length }
val lengthOrder = list.sortedWith(comparator)
//문자열의 길이 기준으로 정렬 > [d, ee, bbb, cccc, aaaaa] 출력

4. sortedBy(), sortBy()

수정이 불가한 리스트(ImmutableList)에 사용하는 sortedBy() 함수와 수정이 가능한 리스트(MutableList)에 사용하는 sortBy() 함수는 리스트 요소가 1개의 데이터 타입으로 이루어지지 않고 내부에 여러 객체를 갖고 있는 타입일 때, 어떤 객체를 비교해서 정렬할 지 결정할 때 사용한다.

sortedBy() 함수는 sorted() 함수와 마찬가지로 정렬된 새로운 리스트를 반환하고, sortBy() 함수는 sort() 함수와 마찬가지로 자기 자신을 정렬한다.

val mutableList = mutableListOf("b" to 10, "a" to 5, "c" to 1)
mutableList.sortBy { it.first } //[(a, 5), (b, 10), (c, 1)]
mutableList.sortBy { it.second } //[(c, 1), (a, 5), (b, 10)]