[알고리즘] 정렬 - 프로그래머스 K번째 수, 가장 큰 수, H-Index

안녕하세요. 오늘은 정렬 관련 글입니다.

짧아요.

 

정렬이란?

데이터가 뒤죽박죽이면 원하는 걸 찾기도, 비교하기도 힘들죠.

정렬은 데이터를 규칙있게 줄 세우는 기술입니다.

 

학교 축제에 부스 참가자 100명을 이름순으로 줄 세워야 한다고 해봅시다.

뒤섞인 명단을 매번 처음부터 훑는 건 비효율적이죠.

한번 깔끔히 정렬해두면:

• 특정 이름 찾기 - 이진 탐색으로 O(log n) (정렬 전엔 O(n))
• 중복 체크/병합/범위 질의 - 정렬돼 있으면 훨씬 쉬움

정렬은 그 자체로도 중요하지만, 다른 알고리즘을 강하게 만들어주는 기본기인거죠.

 

Kotlin 정렬 함수

실제로 자주 사용되는 정렬 함수에 대해서 알아봅시다.

 

sorted()

정렬된 새 리스트를 반환 / 원본 리스트는 그대로.

숫자/문자열의 기본 오름차순으로 정렬

val xs = listOf(3, 1, 2)
val ys = xs.sorted()               // [1, 2, 3], xs는 그대로
val zs = xs.sortedDescending()     // [3, 2, 1], 내림차순

 

sort()

기존 리스트를 정렬 / 반환값 없음

val xs = mutableListOf(3, 1, 2)
xs.sort()                          // xs -> [1, 2, 3]
xs.sortDescending()                // xs -> [3, 2, 1]

 

sortedBy{ key } / sortBy{ key }

키 셀렉터로 정렬(오름차순)

마찬가지로 sortedBy는 새 리스트, sortBy는 기존 리스트

data class P(val name:String, val age:Int)
val people = mutableListOf(P("Kim",20), P("Lee",20), P("Park",25))

people.sortBy { it.age }              // 나이 오름 (안정 → 같은 나이면 입력 순서 유지)
val byName = people.sortedBy { it.name }  // 이름 오름, 새 리스트

 

array.sorted() → List<T> 반환

Array를 sorted하면 List가 반환됨 !

array 반환받고 싶으면 array.sortedArray()를 써야함

 

 

그럼 이제 위 함수들을 실제로 사용해봅시다.

프로그래머스 - K번째 수

배열 array의 i번째 숫자부터 j번째 숫자까지 자르고 정렬했을 때, k번째에 있는 수를 구하려 합니다.

fun solution(array: IntArray, commands: Array<IntArray>): IntArray {
    var answer = intArrayOf()

    for (commands in commands) {
        val i = commands[0]
        val j = commands[1]
        val k = commands[2]

        val arr = array.slice(i - 1..j - 1).sorted()
        answer += arr[k - 1]
    }

    return answer
}

1. 요청사항이 담긴 commands별로 i, j , k를 뽑고
2. array의 i번째, j번째까지 자른 후(slice), 정렬(sorted)된 array를 arr에 할당
3. arr의 k번째 수를 answer에 넣음

프로그래머스 - 가장 큰 수

0 또는 양의 정수가 주어졌을 때, 정수를 이어 붙여 만들 수 있는 가장 큰 수를 알아내 주세요.

fun solutio(numbers: IntArray): String {
    var answer = ""
    val arr = numbers.map { it.toString() }

    val arr2 = arr.sortedWith { a, b -> (b + a).compareTo(a + b) }
    answer = arr2.joinToString("")
    if (answer.startsWith("0")) answer = "0"

    return answer
}

1. 받은 IntArray를 List<String>로 arr에 할당
2. arr의 각 값들을 a,b에 던져, b+a가 더 큰 경우에는 b,a로 정렬한 array를 arr2에 할당
3. 답을 이어붙여서 한 string으로 내야하는데 arr2는 List<String> 형태이므로 joinToString(””)으로 붙여줌
4. 0으로 시작되면 00, 000, 0000 .. 일 수 있으니 0으로 변환해줌
   
   

프로그래머스 - H-Index

어떤 과학자가 발표한 논문 n편 중, h번 이상 인용된 논문이 h편 이상이고 나머지 논문이 h번 이하 인용되었다면 h의 최댓값이 이 과학자의 H-Index입니다.

어떤 과학자가 발표한 논문의 인용 횟수를 담은 배열 citations가 매개변수로 주어질 때, 이 과학자의 H-Index를 return 하도록 solution 함수를 작성해주세요.

fun solution(citations: IntArray): Int {
    var answer = 0
    citations.sort()
    for (i in citations.indices) {
        val h = citations[i]
        if (h >= citations.size - i) {
            answer = citations.size - i
            break
        }
    }
    return answer
}

1. citations를 정렬(오름차순으로)
2. citations 값(=인용 횟수)들을 하나씩 이 인용 횟수보다 많은 인용 횟수를 가진 논문의 개수와 비교 ⇒ h vs h 이상 논문 수
3. h ≥ h 이상 논문 수이면 논문 수가 답.

 

---

이렇게 정렬에 대해 알아보고, 실제 문제들을 풀어보았습니다.

다음에도 풀어볼게요. 앞으로 열심히 ! 꾸준히 ! 풀어볼게요.