[알고리즘 스터디] Reorder Data in Log Files

LeetCode - 937. Reorder Data in Log Files

[LeetCode - 937. Reorder Data in Log Files]

로그 값을 담은 Array<String>이 입력되면 다음 기준에 따라 다시 정렬한다.

 - Input : ["dig1 8 1 5 1","let1 art can","dig2 3 6","let2 own kit dig","let3 art zero"]
           ["a1 9 2 3 1","g1 act car","zo4 4 7","ab1 off key dog","a8 act zoo"]

입력값의 제일 앞쪽부분(' '띄어쓰기 이전)은 식별자로 로그 내용이 똑같을 경우를 제외하면 정렬기준에서 제외된다.

식별자를 제외한 나머지 부분을 기준으로 배열을 정렬한다. 기준은 다음과 같다.

1. 문자로 이루어진 로그가 앞쪽에 온다.
2. 문자가 동일할 경우 식별자까지 포함해 비교한다.
3. 숫자로만 이루어진 로그는 초기에 입력된 순서대로 정렬된다.

class Solution {
    fun reorderLogFiles(logs: Array<String>): Array<String> {
        return logs.sortedWith(
            Comparator { o1, o2 ->
                val r1 = o1.substringAfter(' ')
                val r2 = o2.substringAfter(' ')

                when {
                    r1[0].isDigit() && r2[0].isDigit() -> return@Comparator 0

                    r1 == r2 -> return@Comparator o1.compareTo(o2)

                    r1[0].isLetter() && r2[0].isDigit() -> return@Comparator -1

                    r1[0].isDigit() && r2[0].isLetter() -> return@Comparator 1

                    else -> return@Comparator r1.compareTo(r2)
                }
            }
        ).toTypedArray()
    }
}

입력된 Array의 String값들을 비교해 정렬하는 문제로 여러가지 조건들을 맞춰서 정렬을 수행해야하는데, 정렬기준을 만들기위해 String을 조작하고 Char값을 비교하는 함수들을 사용해야한다.

substringAfter()

Kotlin에서는 여러가지 방법으로 String값을 분할한다. 그 중 substing()은 입력된 String값의 지정된 범위만큼을 다시 반환하는 함수이다.

ex. "abcdefg".substring(0, 3)일 경우 0번째 인덱스부터 2번째 인덱스(인덱스3 전)인 값까지 반환한다. -> "abc"반환
substring(startIndex, endIndex)도 가능하고 IntRange (0..2와 같이 지정 가능)를 지정도 (가능 IntRange의 경우 마지막값 전이 아니라 마지막 값까지 반환)

하지만 이 문제의 경우 식별자의 길이가 다 다르기때문에 인덱스를 사용해 분할이 힘들다.

split()을 사용하면 regex를 사용해 특정 문자마다 분할해 Char Array를 만드는게 가능하지만 이 경우 전체 비교를 위해서는 각 Array를 순회하며 비교해야하기 때문에 따로 Array를 사용하지 않기 위해 substringAfter()를 사용했다.

substringAfter()은 Char값이나 String값을 입력받아 해당 값과 일치하는 첫번째 값 이후를 String타입으로 반환하는 함수로 식별자 이후를 비교하기위해 ' '공백 Char값을 입력해 각 String을 사용해 분할했다.

sortedWith()

여러가지 기준으로 정렬하기 위해 srotedWith()를 사용해서 정렬을 수행했다.
(sortWith()와 동일함, 배열을 복사해서 원본 배열이 바뀌지 않는 기능만 추가됨)

sortedWith()는 Comparator를 전달받아 Tim sort를 수행하는 함수로 여러가지 다중 조건을 설정해 정렬을 수행해야 할 경우 보다 편하게 정렬을 수행할 수 있도록 도와주는 함수다.

Tim sort

우선 sortedWith()의 사용법을 제대로 알기위해서는 Tim sort가 어떤식으로 작동하는지 아는게 더 이해가 쉽다. Tim sort는 Insertion sort(삽입정렬)와 Merge sort(병합정렬)이 혼합된 형태로 정렬되는 알고리즘이다.

전체 배열을 Run이라는 작은 덩어리로 나눠 각 Run을 Insertion sort로 정렬한뒤 각 Run을 Merge sort로 정렬하는 알고리즘을 사용하는데, 이때 Run을 정렬하기위해 Comparator를 사용한다.

Comparator

Comparator는 두가지 값을 입력받아 Int값을 반환하는 객체로 음수 (-1), -, 양수(1) 3가지 중 하나를 반환해야한다.

만약 Comparator에 Int타입의 값 두가지가 입력될 경우 원하는 조건을 설정한 뒤 3가지의 값중의 한가지를 return해주면 된다.

Comparator { o1, o2 -> o1 - o2} // 람다식이기 때문에 자동적으로 마지막 값이 return

sortedWith()에서는 Comparator를 통해 전달받은 값으로 정렬을 수행하는데 첫번째 값으로 o1이, 두번째 값으로 o2가 전달 된다고 했을때, -1이 반환되면 첫번째 전달된 값 즉, o1이 앞으로 정렬되고, 0이라면 입력된 그대로, 1이 반환되면 첫번째 값이 뒤로 정렬된다. (o2가 앞으로 정렬됨)

이런 방식으로 앞서 설명한 Run을 각각 정렬하게 된다.

Comparator의 경우 다양한 조건으로 원하는 값을 return하도록 설정하는게 가능하다. 위의 경우처럼 when을 사용해 특정 조건이 만족될 경우 원하는 대로 값을 반환해 정렬되도록 설정할 수 있다.

Comparator { o1, o2 ->
	// 전달 받은 각 String을 식별자를 제거함
	val r1 = o1.substringAfter(' ')
    val r2 = o2.substringAfter(' ') 

    when {
    	// 식별자를 제거한 값이 둘 다 숫자일 경우 변동이 없도록 하기 위해 0을 반환
    	r1[0].isDigit() && r2[0].isDigit() -> return@Comparator 0 

		r1 == r2 -> return@Comparator o1.compareTo(o2)

		// 각각 문자로 이루어진 경우가 앖으로 갈 수 있도록 양수 혹은 음수를 반환
        r1[0].isLetter() && r2[0].isDigit() -> return@Comparator -1

        r1[0].isDigit() && r2[0].isLetter() -> return@Comparator 1

        else -> return@Comparator r1.compareTo(r2)
	}
}

compareTo()

Comparator가 양수나 음수를 반환해야 한다는건 알았다. 그렇다면 위에서 사용된 compareTo()함수는 대체 뭘 의미할까?

compareTo()함수는 String클래스가 가지고 있는 함수로 Int타입의 경우 값을 서로 비교해 양수나 음수를 만드는게 가능하지만 String타입에서는 직접적으로 양수와 음수를 만들 수 없기 때문에 사용하는 함수이다.

// 만약 전달된 값 중 앞의 값이 크다면 음수가 뒤의 값이 크다면 양수가 된다.
return Int1 - Int2 (o)

// 하지만 String일 경우 애초에 -나 +연산자를 통해 비교가 안된다.
return String1 - String2 (x)

compareTo()함수는 String1.compartTo(String2)의 형태로 사용이 가능하며, 오름차순을 기준으로 한다.

예를들어 오름차순 기준으로 앞의 값이 앞에 위치 해야한다면 -1을 뒤의 값이 앞에 위치해야 한다면 1을 반환한다. (동일한 문자열의 경우 0반환)

compareBy()

앞서 sortedWith()함수에는 Comparator가 전달 되어야 한다고 했다. 하지만 Comparator의 경우 유연한 설정은 가능하지만 if나 when같은 조건문들이 많아질 경우 복잡해진다는 단점이 있다.

이 경우 compareBy()함수를 사용하면 여러가지 다중 조건을 보다 쉽게 설정할 수 있다.

compareBy()함수는 매개변수로 vararg를 전달받는데 이는 원하는 조건 여러가지를 전달하는게 가능하다는 뜻이다.

val people = listOf(
    Person("Alice", 30, 165),
    Person("Bob", 25, 175),
    Person("Charlie", 30, 170),
    Person("David", 25, 160)
)

val sortedPeople = people.sortedWith(
    compareBy(
        { it.age },
        { it.height },
        { it.name }
    )
)

위와 같이 여러가지 조건을 람다로 전달하는게 가능하며 위에서 부터 순차적으로 조건을 검사한뒤 원하는 조건에 해당할경우 결과를 반환한다.

하지만 Comparator와는 다르게 두 값을 모두 선택하는게 불가능하기 때문에 객체의 특정 속성값을 비교하는 경우에 사용하는게 좋다.